На этом шаге мы рассмотрим связь между классами P и NP.
Задача о переносе "Ханойской башни" по самой постановке не может быть распараллелена, так как в один момент времени только один диск переносится с иглы на иглу. Поэтому, даже при появлении такой мощной техники как недетерминированные машины эта задача остается в классе ЕХР.
Задача, решаемая за полиномиальное время на обычной машине, может быть решена за полиномиальное время и на недетерминированной машине, т. е.
P⊆NP
Верно ли обратное (и тогда p=NP) или существуют задачи, решаемые за полиномиальное время на недетерминированной машине, но требующие экспоненциального времени на однопроцессорной машине (тогда p ⊂ NP, NP\P ≠ ∅)?
В первом случае ничего нового в классификации задач от введения класса NP не получим. Но появляется много надежд. Дело в том, что для некоторых задач из класса NP известны только экспоненциальные алгоритмы для их решения на однопроцессорной машине. Если P = NP, т. е. надежда разработать и полиномиальные алгоритмы. Вопрос этот не праздный. На карту поставлено не только машинное время. В криптографии (науке о шифровании информации) существует целое направление - шифрование с открытым ключом. В его основе использование математических задач, решаемых алгоритмами экспоненциальной сложности. Если вдруг для них найдутся эффективные полиномиальные алгоритмы, то многие секреты перестанут быть секретами.
Но и во втором случае появляется много вопросов. Что собой представляет класс NP\P? Чем задачи из этого класса отличаются от других задач из ЕХР? В настоящее время развита довольно большая теория задач класса NP в предположении, что NP ≠ Р. Кому-то может показаться, что это сродни теории привидений. Не известно, есть ли привидения, а уже обсуждается их одежда, вкусы, походка и любимый род занятий.
Однако такой взгляд не верен. Нерешенная проблема не должна тормозить развитие науки. В математике, в компьютерных науках существует несколько недоказанных (или недоказуемых) фундаментальных утверждений-гипотез, принятие которых позволило получить большое количество важных результатов. Достаточно вспомнить тезис Тьюринга, тезис Черча, аксиому Цермело. Поэтому дальше будет обсуждаться строение класса NP.
На следующем шаге мы рассмотрим классы сложности P, NP, NPI, NPC.
