§ 30. Классы PuNp

199

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

1. х является кодом некоторой булевой формулы,

1. значение закодированной словом х булевой формулы при тех значениях фактически присутствующих в ней переменных, которые последовательно указаны в слове у, равно 1.

(Число нулей и единиц в слове у равно числу переменных, факти­чески присутствующих в закодированной булевой формуле: напри­мер, в булевой формуле x₃Vx₁₅ фактически присутствуют две пере­менные, хотя для них и использованы большие индексы; сертифика­том выполнимости этой формулы служит, например, слово 11.) Та­кой алгоритм можно сделать полиномиальным. Это говорит о том, что при указанном способе кодирования булевых формул предикат, распознающий выполнимость булевой формулы, принадлежит клас­су NP, — сертификатом является слово у, указывающее значения пе­ременных, при которых значение булевой формулы равно 1, а зна­чение предиката R{x,у), входящего в (30.1), вычисляется с помощью алгоритма, проверяющего (a) и (b). Полином р{п) можно взять рав­ным п, так как |j| ^ |х| в силу того, что у содержит значения только тех переменных, которые фактически присутствуют в булевой фор­муле.

Неизвестно, принадлежит ли классу Р предикат на словах из Л*, распознающий выполнимость. Алгоритмы проверки выполнимости, основанные на переборе всех возможных комбинаций значений пе­ременных х_ъ х₂,..., х_п, не являются полиномиальными.

Рассмотренный пример дает мотивацию определения 30.1 и про­ясняет смысл понятия «сертификат». Отметим два важных момента.

1. Перебор всех возможных слов у, |у|^р(|х|), для проверки равенства и(х) = 1 с помощью (30.1) может потребовать рассмотре­ния экспоненциального по отношению к |х| числа возможностей. Но определение 30.1 требует лишь, чтобы при и(х) = 1 сертификат суще­ствовал, вопрос же о сложности его построения не затрагивается.

1. Если и е NP, то равенство u(x) = 0 означает, что соответству­ющего сертификата для слова у не существует. Другими словами, принадлежность х множеству истинности предиката подтверждается сертификатом, а непринадлежность —отсутствием сертификата. По-

2. 200