§ 30. Классы р и np

Цель этого и следующих параграфов—дать общее, без многих дета­лей, представление о некоторых проблемах, касающихся алгоритмов

196

Глава 7. Сводимость

полиномиально ограниченной сложности (см. § 5, определение 5.2) или, другими словами, полиномиальных алгоритмов.

Подход, согласно которому алгоритмы подразделяются на поли­номиальные и все остальные, далеко не всегда является продуктив­ным с практической точки зрения (алгоритм со сложностью п¹⁰⁰, где п—размер входа, вряд ли найдет массовое применение), но при бо­лее широком взгляде этот подход имеет свою логику. Если для ре­шения важной задачи никак не удается найти алгоритм, сложность которого хотя бы при каком-нибудь показателе d допускала бы оцен­ку 0{n^d), то сам вопрос о существовании такого алгоритма нельзя назвать праздным.

Иногда бывает очень трудно установить принадлежность или со­ответственно непринадлежность задачи классу P, состоящему из та­ких задач, для которых существует полиномиальный алгоритм ре­шения. В классе P выделяют подкласс Р тех вычислительных задач, где результатом может быть лишь 1 или 0, т. е. фактически «да» или «нет», что типично для задач распознавания. К этим задачам относит­ся, например, задача распознавания выполнимости булевой форму­лы, задача распознавания существования в графе гамильтонова цик­ла и т. д. Неизвестно, существуют ли полиномиальные алгоритмы их решения, но сравнительно легко устанавливается их принадлежность специальному классу NP. Определение класса NP будет дано ниже, из него будет следовать, что Р с NP. Если бы было доказано, что Р = NP, то в широком спектре случаев мы бы легко устанавливали принад­лежность задачи распознавания классу Р, т. е. устанавливали бы су­ществование полиномиального алгоритма распознавания; его разра­ботка—это отдельный вопрос. Но равенство P = NP по сей день не доказано, и есть основания подозревать, что оно неверно. Возникает проблема Р = NP, о которой мы тоже будем говорить.

Вначале скажем о ряде ограничений, налагаемых на рассматрива­емые задачи. Во-первых, речь будет идти о задачах распознавания тех слов в данном алфавите Л, которые принадлежат оговоренному под­множеству (языку) L множества всех слов Л* в этом алфавите. Все объекты, о которых идет речь в рассматриваемых задачах, должны быть представлены (закодированы) словами в алфавите Л, входом алгоритма является одно-единственное слово в алфавите Л. Размер входа х—это всегда длина |х| (число букв) в слове х. Вычислитель­ные затраты должны учитываться достаточно тщательно, неучтенной может оставаться лишь незначительная часть операций (во всяком случае, допускающая полиномиальную верхнюю оценку). Если име­ется в виду модель вычислений РАМ, то предполагается, что вычисле-