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

этому возможные значения 1 и 0 не являются симметричными или равноправными; как показано в примере 30.1, предикат, распозна­ющий выполнимость булевой формулы, принадлежит NP, но мы не можем на основе только этого утверждать, что и предикат, распо­знающий невыполнимость булевой формулы, принадлежит NP (какое слово могло бы быть сертификатом невыполнимой формулы?).

Предложение 30.1. Р с NP.

Доказательство. Определим Д(х, у) = и(х) в (30.1) при любом сло­ ве у и будем считать пустое слово сертификатом любого х такого, что и(х) = 1; в качестве полинома р берем нулевой полином. □

Продолжим рассмотрение примеров.

Пример 30.2. Согласно результатам Агравала, Кайала и Саксены (пример 22.2), классу Р принадлежит предикат, определенный на сло­вах в алфавите {0,1} и принимающий значение 1, если и только если слово является записью простого числа. Рассмотрим близкую задачу. Для заданных п, fceN⁺, к < п, выяснить, имеется ли у числа п дели­тель Z такой, что 1 < Z s= к. Числа п и к задаются в двоичной системе; используя разделитель «;», мы можем кодировать пару п, к словом в алфавите

Л₂ = {0,1,;}.

Если слово х кодирует указанным образом пару п, к, то в качестве сертификата можно взять двоичную запись некоторого конкретного делителя I, 1 < I < к. Тогда входящий в (30.1) предикат Д(х, у) должен принимать значение 1, если и только если

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

1. у является двоичной записью некоторого числа Z такого, что Z ^ к и при этом Z | к.

Существует алгоритм проверки условий (a), (b), вычислительные за­траты которого ограничены величиной С(|х| + |у|)², где С — некото­рая константа. Можно в (30.1) положить р{п) = п, так как Ык. Это говорит о том, что рассматриваемый предикат на Л* принадлежит классу NP. Неизвестно, принадлежит ли он также классу Р.

Пример 30.3. В связи с изучением классов Р и NP рассматрива­ется большое число задач на графах, при этом графы, как правило, задаются матрицами смежности. В алфавите Л₂ матрица смежности

§ 31. Существование задач распознавания, не принадлежащих р 201

кодируется словом, в котором строки матрицы выписаны одна за дру­гой через разделитель «;». Легко видеть, что классу NP принадлежит предикат, принимающий значение 1, если и только если слово яв­ляется кодом графа, обладающего гамилътоновым циклом, т. е. цик­лом, проходящим по одному разу через все вершины графа (рис. 24);

Рис. 24. а) Гамильтонов цикл; б) граф без гамильтонова цикла.

сертификатом может, например, являться последовательность двоич­ных номеров вершин гамильтонова цикла. Эти номера выписываются в одно слово через разделитель «;».

Аналогичным образом, классу NP принадлежит предикат, прини­мающий значение 1, если и только если слово является кодом графа, обладающего кликой с заданным числом т вершин. При этом кли­кой называется набор т вершин, любые две из которых соединены ребром (в изображенном на рис. 24а графе имеется несколько клик с тремя вершинами, но нет ни одной с четырьмя вершинами). Исход­ные данные кодируются словом в алфавите Л₂: сначала идет матрица смежности, записанная так, как было сказано выше, затем, после раз­делителя «;»,—число т в двоичной системе. Эта задача принадлежит классу NP, сертификатом может быть слово, составленное из двоич­ных номеров вершин клики, перечисленных через разделитель «;».

Относительно обоих этих предикатов на Л₂ неизвестно, принад­лежат ли они классу Р.