Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Как правило, нижние оценки сложности любой задачи из класса V определяются довольно просто. Кроме того, для этих задач можно точно определить полиномиальную оценку количества шагов, необходимых для их решения. В качестве примера рассмотрим машину Div3 (пример 4.1). Она распознает п-битовую строку ровно за п шагов, т.е. именно за столько шагов, сколько требуется для записи входного предложения.
Однако для задач из класса MV нижнюю оценку сложности получить очень трудно. Все известные оценки сложности NP-задач являются верхними. Например, как показано выше, для решения задачи SQUAREFREENESS с помощью тривиального деления верхняя оценка равна гДе N — размер входного
числа. По существу, верхняя оценка означает следующее: "для решения задачи требуется именно столько шагов", хотя при этом умалчивается, что задачу можно решить и за меньшее количество шагов. Фактически задачу SQUAREFREENESS можно решить методом числового решета (Number Field Sieve) за меньшее количество шагов, однако число j^/wj остается верхней оценкой.
Не следует путать точную "нижнюю границу" и просто "нижнюю границу". Последнее выражение часто встречается в литературе (например, в знаменитой статье Кука (Cook) [80], в которой доказано, что "задача выполнимости" ("Satisfiability Problem") является "NP-полной"). Оно означает вновь полученную оценку
162
Часть II. Математические основы
сложности, которая оказалась меньше, чем ранее существующие. Даже определение обычной (не точной) нижней границы должно сопровождаться доказательством. В свою очередь, определение точной нижней границы сложности NP-задачи является основным камнем преткновения в теории вычислительной сложности.
Трудность определения точной нижней неполиномиальной оценки сложности NP-задачи порождает серьезные последствия для современной криптографии, в которой вопросы безопасности рассматриваются через призму вычислительной сложности. Эти вопросы будут изучены в разделе 4.8.
4.5.1 Недетерминированные полиномиально полные задачи
Хотя до сих пор неизвестно, выполняется ли равенство V = NV, сложность решения некоторых задач из класса NV эквивалентна сложности решения произвольной задачи из класса NV. Иначе говоря, если существует эффективный алгоритм решения одной из таких задач, то с его помощью можно решить любую задачу из класса NV. Такие задачи называются недетерминированными полными задачами с полиномиальным временем решения (non-deterministic polynomial-time complete problem) или NP-полными (сокращенно NPC).
Определение 4.10 (Полиномиально приводимый язык). Язык L называется полиномиально приводимым (polynomially reducible) к другому языку Lo, если существует детерминированная машина Тьюринга М с полиномиальным временем работы, которая переводит любое предложение I G L в предложение Iq е Lo. так что I & L тогда и только тогда, когда Iq € доопределение 4.11 (NP-полный язык). Язык Lo Е NV называется недетерминированным полным языком с полиномиальным временем распознавания (NP-пол-ным), если любой язык L € NV приводится к языку Lo за полиномиальное время.
К числу хорошо известных NP-полных задач относится так называемая зада- I ча выполнимости (SATISFIABILITY), поставленная Куком в работе [80]. Это — первая NP-полная задача [227]. Обозначим через Е[х\, а?2,..., хп) булевское выражение, построенное из п булевских переменных х\, х2, - • -, хп и булевских one- I раторов Л, V и -1.
Задача SATISFIABILITY
ВВОД: X = (a?i, ->хъ х2, ->ж2, - • ¦, хп, ->хп);
Е{х\,х2,...,хп).
Глава 4. Вычислительная сложность
163
Истинностной подстановкой (truth assignement) для выражения Е(х\,х2,... ,хп) является подсписок X' списка X, такой что для 1 ^ г ^ п подсписок X' содержит либо Xi, либо ->Xi, но не оба одновременно, причем Е(Х') = True.
ВОПРОС: Является ли выражение Е(х\,х2,хп) выполнимым?
Иначе говоря, существует ли истинностная подстановка? Если выражение Е{х\, х2,.. .,хп) является выполнимым, алгоритм выдает ответ "ДА".
Если истинностная подстановка существует, ответ ДА можно проверить за время, ограниченное полиномом степени п. Следовательно, по определению 4.8 SATISFIABILITY € ЛГР. Следует обратить внимание на то, что существует 2™ возможных истинностных подстановок, и до сих пор не известен ни один детерминированный полиномиальный алгоритм, который определил бы, существует ли истинностная подстановка.
Доказательство того, что задача SATISFIABILITY является NP-полной (Кук [80]), дано в главе 10 книги [9]. Это доказательство является конструктивным и основано на преобразовании произвольной недетерминированной машины Тьюринга с полиномиальным временем выполнения в машину, которая решает задачу SATISFIABILITY.
Большой список NP-полных задач приведен в книге [118].
Любую новую оценку сложности NP-полной задачи, не превышающую верхнюю оценку, за полиномиальное время можно преобразовать в новый результат для всего класса NP-задач. Следовательно, как указано в работе [98], желательно, чтобы стойкость криптографических алгоритмов была обеспечена NP-полной задачей. Последовательная атака на подобную криптосистему должна привести к решению всего класса таких задач, что крайне маловероятно. Однако это вполне разумное требование не очень практично ни с точки зрения стойкости криптосистем, ни с точки зрения решения всех NP-задач с помощью атаки на такие криптосистемы. Это странное явление будет изучено в разделе 4.8.2.
