Введение в криптографию
[an error occurred while processing this directive]

Криптография и гипотеза PNP


Как правило, знакомство математиков-неспециалистов с теорией сложности вычислений ограничивается классами P и NP и знаменитой гипотезой PNP.

Напомним вкратце необходимые сведения из теории сложности вычислений. Пусть - множество всех конечных строк в двоичном алфавите . Подмножества в теории сложности принято называть языками. Говорят, что машина Тьюринга работает за полиномиальное время (или просто, что она полиномиальна), если существует полином такой, что на любом входном слове длины  машина останавливается после выполнения не более, чем операций. Машина Тьюринга распознает (другой термин - принимает) язык , если на всяком входном слове машина

останавливается в принимающем состоянии, а на всяком слове - в отвергающем. Класс P - это класс всех языков, распознаваемых машинами Тьюринга, работающими за полиномиальное время. Функция

вычислима за полиномиальное время, если существует полиномиальная машина Тьюринга такая, что если на вход ей подано слово , то в момент останова на ленте будет записано значение . Язык принадлежит классу NP, если существуют предикат , вычислимый за полиномиальное время, и полином такие, что . Таким образом, язык принадлежит NP, если для всякого слова из  длины  можно угадать некоторую строку полиномиальной от  длины и затем с помощью предиката  убедиться в правильности догадки. Ясно, что

. Является ли это включение строгим - одна из самых известных нерешенных задач математики. Большинство специалистов считают, что оно строгое (так называемая гипотеза PNP). В классе NP выделен подкласс максимально сложных языков, называемых NP-полными: любой NP-полный язык распознаваем за полиномиальное время тогда и только тогда, когда P=NP.

Для дальнейшего нам потребуется еще понятие вероятностной машины Тьюринга. В обычных машинах Тьюринга (их называют детерминированными, чтобы отличить от вероятностных) новое состояние, в которое машина переходит на очередном шаге, полностью определяется текущим состоянием и тем символом, который обозревает головка на ленте. В вероятностных машинах новое состояние может зависеть еще и от случайной величины, которая принимает значения 0 и 1 с вероятностью каждое. Альтернативно, можно считать, что вероятностная машина Тьюринга имеет дополнительную случайную ленту, на которой записана бесконечная двоичная случайная строка. Случайная лента может читаться только в одном направлении и переход в новое состояние может зависеть от символа, обозреваемого на этой ленте.




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


[an error occurred while processing this directive]