Основы современной криптографии

Логопедическое занятие тема гласные звуки

Общие положения - часть 4


Рассмотрим одно из таких предположений.

Обозначим через S множество всех конечных двоичных слов, а через Sn – множество всех двоичных слов длины n. Под­множества L О S в теории сложности принято называть языками. Говорят, что машина Тьюринга М

работает за полиномиальное время (или просто, что она полиномиальна), если существует полином р такой, что на любом входном слове длины п

машина М останавливается после выполнения не бо­лее, чем р(п) операций. Машина Тьюринга М распознает (другой термин – принимает) язык L, если на всяком входном слове x О L машина М оста­навливается в принимающем состоянии, а на всяком слове х П L – в от­вергающем. Класс Р – это класс всех языков, распознаваемых машинами Тьюринга, работающими за полино­миальное время. Функция f:S ® S вы­числима за полиномиальное время, если существует полиномиальная машина Тьюринга такая, что если на вход ей подано слово x О S, то в момент оста­нова на ленте будет записано значение f(x). Язык L принадлежит классу NP, если существуют предикат Р(х,у): SґS ® {0,1}, вычислимый за поли­но­миальное время, и полином р такие, что L = {x| $ y P(x,y)& |y| Ј р(|x|)}.

То есть язык L принадлежит NP, если для всякого слова из L дли­ны п можно угадать некоторую строку полиномиальной от п длины и за­тем с помощью предиката Р убедиться в правильности догадки. Ясно, что Р Н NP. Является ли это включение строгим – одна из самых известных не­решенных задач математики. Большинство специалистов считают, что оно строгое (так называемая гипотеза P

NP). В классе NP

выделен подкласс максимально сложных языков, называемых NP-полными: любой NP-полный язык распознаваем за полиномиальное время тогда и только тогда, когда P = NP.

Нам еще потребуется понятие вероятностной машины Тьюринга. В обычных машинах Тьюринга (их называют детерминированны­ми) новое состояние, в которое машина переходит на очередном шаге, полностью определяется текущим состояни­ем и тем символом, который обозревает головка на ленте.




- Начало -  - Назад -  - Вперед -



Книжный магазин