Проблема NP-полноты. Алгоритмически неразрешимые задачи

Проблема NP-полноты. Алгоритмически неразрешимые задачи

Определение принадлежности задачи к классу Pявляется важным моментом в программировании, поскольку это тесно связано с существованием практического решения задачи. И действительно, задачи, не принадлежащие к классу P, характеризуются крайне высоким временем выполнения даже при обработке умеренного объема входных данных.

Вопрос о принадлежности всех NP-задач классу Pостается открытым. Можно считать, что это наиболее известная проблема из числа еще не решенных в современной теории вычислительных систем. Ее успешное решение может иметь значительные последствия, например, в вопросе о существовании шифровальных систем.

Надежность таких систем основывается на нереальном количестве времени, затрачиваемом на решение задач, подобных задаче о коммивояжере. Если будет доказано существование эффективных методов решения подобных задач, то данные шифровальные системы будут скомпрометированы.

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

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

⇐ Предыдущая 12