§ 30. Классы PuNp

197

ния выполняются на базе конечного множества операций с тем или иным числом операндов, преобразующих буквы алфавита Л в буквы алфавита Л; исследуется сложность по числу этих операций — подо­бие битовой сложности. Требуется также учет числа присваиваний в ходе выполнения алгоритма.

Таким образом, содержательная задача распознавания (например, задача существования пути с фиксированными свойствами в задан­ном графе) должна быть для обсуждения ее принадлежности классам Р и NP переформулирована в виде задачи распознавания принадлеж­ности заданного слова некоторому языку. Такая формализация необ­ходима потому что одна и та же математическая идея при одном из двух разных способов представления данных может приводить к по­линомиальному алгоритму, а при другом—нет.

Часто при обсуждении проблемы Р = NP исходят из машины Тью­ринга (МТ) как модели вычислений, при этом вычислительные за­траты измеряются числом тактов работы машины. Это связано с тем, что модель МТ удобнее модели РАМ при доказательстве разного ро­да теорем об алгоритмах, в особенности — теорем о невозможности алгоритмов с теми или иными свойствами. Но модель РАМ ближе, чем МТ, к реальным вычислительным устройствам, и хотелось бы, чтобы результаты исследования классов Р и NP, проводимые на ос­нове модели МТ, сохраняли свою значимость для модели РАМ. Их значимость действительно сохраняется, о чем будет сказано в конце этого параграфа, а до той поры мы, как правило, не будем делать уточнений относительно модели вычислений. Но, повторяем, опера­ции преобразования букв, входящих в слова, должны подсчитываться тщательно.

По сути дела, в каждой задаче распознавания принадлежности слова языку L обсуждается некоторый предикат и(х), областью опре­деления которого является все множество Л*, и и(х) = 1, если и толь­ко если х е L. В дальнейшем нам часто будет удобно говорить не о языках, а о предикатах (по существу, это, конечно, одно и то же, но предикаты несколько предпочтительнее из-за того, что к ним можно применять логические операции, кванторы и т.д.). Соответственно, мы будем говорить о принадлежности предиката классу Р и т. д. Ино­гда нам будет удобно рассуждать о предикатах не одной, а нескольких таких переменных, которые принимают значения в Л*. В этих случа­ях без специального упоминания предполагается, что в алфавит Л включены некоторые разделители: если, скажем, разделитель «запя­тая» (т.е. «,») включен в Л, то v(x,у) имеет один аргумент х,у, где х и у суть слова в Л*, не содержащие разделителя «,» (кавычки по-

198

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

ставлены, чтобы не нарушать пунктуацию фразы). Соответственно, длиной пары слов x,y является |x| + |y\ + 1.

Теперь обсудим класс предикатов NP. Само его странное обо­значение NP есть не что иное, как аббревиатура от английских слов nondeterministic polynomial —недетерминированный полиноми­альный. Изначальное определение класса NP, появившееся в теории сложности в начале 70-х годов XX столетия, опиралось на понятие недетерминированного алгоритма¹. Позднее появилось эквивалент­ное определение, не прибегающее к недетерминированности.

Определение 30.1. Заданный на Л* предикат u(x) принадлежит классу NP, если существуют предикат R(x,y) е Р и полином p{n) та­кие, что u{x) можно представить в виде

u{x) = З_yеЛ,_;|_{y Кp(}|_x|)R x, y). (30.1)

В том случае, когда u(x) = 1, слово y называется сертификатом сло­ва x.

Пример 30.1. Булева формула f(x_l5x₂, ...,x_n) выполнима, если су-

ществуют значения x°,x°, ...,x_n° g {0,1} переменных x_г,x₂, ...,x_n та-

кие, что

f(x°,x°, ...,x_n°) = 1;

в противном случае булева формула невыполнима. Так, булева фор­мула

­(­ xiVxa) (30.2)

выполнима, так как ее значение при x_г = 1, x₂ = 0 равно 1, а булева формула x_г Л ­ x! одной переменной x_г невыполнима, так как и при x_г = 1, и при x_г = 0 значение этой формулы есть 0.

Любая булева формула может быть закодирована словом в алфа­вите

Л₁ = {x,0,1, (,),­, л, V},

для этого переменные x_г,x₂,x_ъ, ... кодируются как xl,x10,xll, ...: вслед за буквой x помещается номер переменной в двоичной систе­ме. Формула (30.2) кодируется как ­(­xl VxlO), при этом, например, слово )xlx­ в алфавите А_г не является кодом какой-либо булевой формулы. Можно предложить простой алгоритм, который проверяет, является ли данное слово в алфавите Л_х кодом какой-либо булевой формулы, а также алгоритм, который по данному коду некой буле­вой формулы и данным булевым значениям (нулям и единицам) тех

См., например, [13].