10. NP-ПОЛНЫЕ ЗАДАЧИ
Сколько вычислений должна требовать задача, чтобы мы сочли ее действительно трудной? Общепринято, что если задачу нельзя решить быстрее, чем за экспоненциальное время, то ее следует рассматривать как безусловно трудно разрешимую. В этой "схеме классификации" задачи, решаемые алгоритмами полиномиальной сложности, будут легко разрешимыми. Но нужно иметь в виду, что, хотя экспоненциальная функция (такая, как 
) растет быстрее любой полиномиальной функции от 
для небольших значений 
алгоритм, требующий 
времени, может оказаться эффективнее многих алгоритмов с полиномиально ограниченным временем работы. Например, сама функция 
не превосходит 
до значения 
равного 59. Тем не менее скорость роста экспоненциальной функции столь стремительна, что мы будем называть задачу трудно разрешимой, если у всех алгоритмов, решающих ее, сложность по меньшей мере экспоненциальна.
В этой главе мы приведем соображения, показывающие, что некоторый класс задач, а именно задач, полных для недетерминированного полиномиального времени (называемых NP-полными), вероятно, содержит только трудно разрешимые задачи. Этот класс включает в себя многие "классические" задачи из комбинаторики (такие, как задачу о коммивояжере, о гамильтоновом цикле, задачу целочисленного линейного программирования), и можно показать, что все задачи из этого класса "эквивалентны" в том смысле, что если хотя бы одна из них оказалась легко разрешимой, то таковы же и все остальные. Поскольку многие из этих задач изучались математиками и специалистами по вычислениям в течение десятилетий и ни для одной из них не удалось найти алгоритма полиномиальной сложности, естественно предположить, что таких полиномиальных алгоритмов и не существует, и, значит, можно рассматривать все задачи из этого класса как трудно разрешимые.
Мы исследуем также еще один класс задач, называемых "полными для полиномиальной емкости", которые по меньшей мере столь же сложны, как NP-полные задачи, но и про них еще не доказано, что
они трудно разрешимы. В гл. 11 будут изложены некоторые задачи, относительно которых действительно можно доказать, что они трудно разрешимы.
