Сложность проблем

Теория сложности также классифицирует и сложность самих проблем, а не только сложность конкретных алгоритмов решения проблемы. (Отличным введением в эту тему являются [600, 211, 1226], см. также [1096, 27, 739].) Теория рассматривает минимальное время и объем памяти, необходимые для решения самого трудного варианта проблемы на теоретическом компьютере, известном как машина Тьюринга. Машина Тьюринга представляет собой конечный автомат с бесконечной лентой памяти для чтения-записи и является реалистичной моделью вычислений.

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

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

Проблемы можно разбить на классы в соответствии со сложностью их решения. Самые важные классы и их предполагаемые соотношения показаны на Рис. 11 -1. (К несчастью, лишь малая часть этих утверждений может быть доказана математически.)

Рис. 11-1. Классы сложности

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

Важность NP в криптографии состоит в следующем: многие симметричные алгоритмы и алгоритмы с открытыми ключами могут быть взломаны за недетерминированное полиномиальное время. Для данного шифротекста C, криптоаналитик просто угадывает открытый текст, X, и ключ, k, и за полиномиальное время выполняет алгоритм шифрования со входами X и k и проверяет, равен ли результат C. Это имеет важное теоретическое значение, потому что устанавливает верхнюю границу сложности криптоанализа этих алгоритмов. На практике, конечно же, это выполняемый за полиномиальное время детерминированный алгоритм, который и ищет криптоаналитик. Более того, этот аргумент неприменим ко всем классам шифров, конкретно, он не применим для одноразовых блокнотов - для любого C существует множество пар X, k, дающих C при выполнении алгоритма шифрования, но большинство этих X представляют собой бессмысленные, недопустимые открытые тексты.

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

Если все NP проблемы решаются за полиномиальное время на детерминированной машине, то P = NP. Хотя кажется очевидным, что некоторые NP проблемы намного сложнее других (вскрытие алгоритма шифрования грубой силой против шифрования произвольного блока шифротекста), никогда не было доказано, что P  NP (или что P = NP). Однако, большинство людей, работающих над теорией сложности, убеждены, что эти классы неравны.

Что удивительно, можно доказать, что конкретные NP-проблемы настолько же трудны, как и любая проблема этого класса. Стивен Кук (Steven Cook) доказал [365], что проблема Выполнимости (Satisfiability problem, дано правильное логическое выражение, существует ли способ присвоить правильные значения входящим в него переменным так, чтобы все выражение стало истиной?) является NP-полной. Это означает, что, если проблема Выполнимости решается за полиномиальное время, то P = NP. Наоборот, если может быть доказано, что для любой проблемы класса NP не существует детерминированного алгоритма с полиномиальным временем решения, доказательство покажет, что и для проблемы Выполнимости не существует детерминированного алгоритма с полиномиальным временем решения. В NP нет проблемы труднее, чем проблема Выполнимости.

С тех пор, как основополагающая работа Кука была опубликована, было показано, что существует множество проблем, эквивалентных проблеме Выполнимости, сотни их перечислены в [600], ряд примеров приведен ниже. Из-за эквивалентности я полагаю, что эти проблемы также являются NP-полными, они входят в класс NP и так же сложны, как и любая проблема класса NP. Если бы была доказана их решаемость за детерминированное полиномиальное время, вопрос P против NP был бы решен. Вопрос, верно ли P = NP, является центральным нерешенным вопросом теории вычислительной сложности, и не ожидается, что он будет решен в ближайшее время. Если кто-то покажет, что P = NP, то большая часть этой книги станет ненужной: как объяснялось ранее многие классы шифров тривиально взламываются за недетерминированное полиномиальное время. Если P = NP, то они вскрываются слабыми, детерминированными алгоритмами.

Следующим в иерархии сложности идет класс PSPACE. Проблемы класса PSPACE могут быть решены в полиномиальном пространстве, но не обязательно за полиномиальное время. PSPACE включает NP, но ряд проблем PSPACE кажутся сложнее, чем NP. Конечно, и это пока недоказуемо. Существует класс проблем, так называемых PSPACE-полных, обладающих следующим свойством: если любая из них является NP-проблемой, то PSPACE = NP, и если любая из них является P-проблемой, то PSPACE = P.

И наконец, существует класс проблем EXPTIME. Эти проблемы решаются за экспоненциальное время. Может быть действительно доказано, что EXPTIME-полные проблемы не могут быть решены за детерминированное полиномиальное время. Также показано, что P не равно EXPTIME.

NP-полные проблемы

Майкл Кэри (Michael Carey) и Дэвид Джонсон (David Johnson) составили список более чем 300 NP-полных проблем [600]. Вот некоторые:

• Проблема путешествующего коммивояжера. Путешествующему коммивояжеру нужно посетить различные города, используя только один бак с горючим (существует максимальное расстояние, которое он может проехать). Существует ли маршрут, позволяющий ему посетить каждый голод только один раз, используя этот единственный бак с горючим? (Это обобщение проблемы гамильтонова пути - см. раздел 5.1.)

• Проблема тройного брака. В комнате n мужчин, n женщин и n чиновников (священников, раввинов, кого угодно). Есть список разрешенных браков, записи которого состоят из одного мужчины, одной женщины и одного регистрирующего чиновника. Дан этот список троек, возможно ли построить n браков так, чтобы любой либо сочетался браком только с одним человеком или регистрировал только один брак?

• Тройная выполнимость. Есть список n логических выражений, каждое с тремя переменными. Например: если (x и y) то z, (x и w) или (не z), если ((не u и не x) или (z и (u или не x))) то (не z и u) или x), и т.д. Существует ли правильные значения всех переменных, чтобы все утверждения были истинными? (Это частный случай упомянутой выше проблемы Выполнимости.)