Теорема Бермана — Форчуна

Лемма (1):

Язык [math]L[/math] является [math]\mathrm{coNP}[/math]-полным тогда и только тогда, когда [math]\overline L[/math] является [math]\mathrm{NP}[/math]-полным (то есть [math]L \in \mathrm{coNP\mbox{-}C} \Leftrightarrow L \in \mathrm{co\mbox{-}NPC}[/math]).

Доказательство:

[math]\triangleright[/math]

Пусть [math]L[/math] — [math]\mathrm{coNP}[/math]-полный. Тогда [math]L \in \mathrm{coNP}[/math] и [math]\overline L \in \mathrm{NP}[/math]. Рассмотрим произвольный язык [math]L_1 \in \mathrm{NP}[/math]. Тогда [math]\overline {L_1} \in \mathrm{coNP}[/math]. Так как [math]L[/math] — [math]\mathrm{coNP}[/math]-полный, то [math]\overline {L_1} \le L[/math], следовательно [math]L_1 \le \overline L[/math] (по лемме). Получили, что [math]\overline L \in \mathrm{NP}[/math] и [math]\forall L_1 \in \mathrm{NP} \Rightarrow L_1 \le \overline L[/math]. Значит [math]\overline L \in \mathrm{NPC}[/math]. В обратную сторону доказательство аналогично.

[math]\triangleleft[/math]

Определение:

[math]\mathrm{TAUT} = \{\phi[/math] — булева формула [math]\bigm{|} \forall x = (x_1, x_2, \ldots , x_m) \, \phi(x)=1\}[/math].

Лемма (2):

[math]\mathrm{TAUT} \in \mathrm{coNPC}[/math].

Доказательство:

[math]\triangleright[/math]

[math]\overline {\mathrm{TAUT}} = \{\phi \bigm{|} \exists x : \phi(x) \ne 1\} = \{\phi \bigm{|} \overline {\phi} \in \mathrm{SAT}\}[/math], то есть [math]\mathrm{SAT} \le \overline {\mathrm{TAUT}} \, (f(\phi) = \overline {\phi})[/math]. Кроме того, [math]\overline {\mathrm{TAUT}} \in \mathrm{NP}[/math] [math]([/math]в качестве сертификата используется [math]x[/math], на котором [math]\phi(x) \ne 1)[/math]. Значит [math]\overline{\mathrm{TAUT}} \in \mathrm{NPC}[/math]. Тогда по лемме (1) [math]\mathrm{TAUT} \in \mathrm{coNPC}[/math].

[math]\triangleleft[/math]

Определение:

[math]\mathrm{SPARSE} = \{L \bigm{|} \exists[/math] полином [math]p: \forall n \, |L \cap \Sigma^n| \le p(n)\}[/math].

Теорема (Берман, Форчун):

[math]\mathrm{coNPC} \cap \mathrm{SPARSE} \ne \varnothing \Rightarrow \mathrm{P} = \mathrm{NP}[/math].

Доказательство:

[math]\triangleright[/math]

Пусть существует [math]S \in \mathrm{coNPC} \cap \mathrm{SPARSE}[/math]. Разрешим [math]\mathrm{TAUT}[/math] за полином. Для начала напишем программу, разрешающую [math]\mathrm{TAUT}[/math]: [math]check(\phi, i)[/math]: if [math]\phi=0[/math] return 0 if [math]\phi=1[/math] return 1 if [math]memo[\phi] \ne -1[/math] return [math]memo[\phi][/math] [math]memo[\phi] \leftarrow check(\phi|_{x_i=0}, i+1) \wedge check(\phi|_{x_i=1}, i+1)[/math] return [math]memo[\phi][/math] Ответом будет [math]check(\phi, 1)[/math]. Так как [math]\mathrm{TAUT} \in \mathrm{coNPC}[/math] и [math]S \in \mathrm{coNPC}[/math], то [math]\mathrm{TAUT} \le S[/math], то есть [math]\exists f \in \mathrm{\widetilde{P}} : \phi \in \mathrm{TAUT} \Leftrightarrow f(\phi) \in S[/math]. Поэтому, если в предыдущей программе заменить все обращения к [math]memo[\phi][/math], на [math]memo[f(\phi)][/math], то полученная программа по-прежнему будет разрешать [math]\mathrm{TAUT}[/math]. Оценим необходимый размер [math]memo[/math]. Можно считать, что [math]\mathrm{T}(f, \phi) \le q(n)[/math], где [math]n = |\phi|[/math], а [math]q[/math] — монотонно возрастающий полином. Тогда [math]|f(\phi)| \le q(n)[/math]. Так как [math]S \in \mathrm{SPARSE}[/math], то [math]|S \cap \Sigma^k| \le p(k)[/math], где [math]p[/math] — полином. Можно считать, что [math]p[/math] монотонно возрастает. Тогда размер [math]memo[/math] (число слов длины не более [math]q(n)[/math] в языке) можно оценить сверху: [math]memo.size() \le \sum\limits_{i=0}^{q(n)}p(i) \le (1+q(n)) \cdot p(q(n)) \le r(n)[/math], где [math]r(n)[/math] — полином. [math]check(\phi, i)[/math]: if [math]\phi=0[/math] return 0 if [math]\phi=1[/math] return 1 if [math]memo[f(\phi)] \ne -1[/math] //(1) return [math]memo[f(\phi)][/math] [math]memo[f(\phi)] \leftarrow check(\phi|_{x_i=0}, i+1) \wedge check(\phi|_{x_i=1}, i+1)[/math] //(2) if [math]memo.size() \gt r(n)[/math] exit [math]0[/math] return [math]memo[f(\phi)][/math] Двоичное дерево, получающееся в результате рекурсивных вызовов модифицированной программы. Красным и желтым помечены узлы, в которых происходит обращение к элементу memo[j]. В красных узлах условие (1) ложно, в желтых — истинно. Рассмотрим двоичное дерево, получающееся в результате рекурсивных вызовов данной программы. Рассмотрим произвольный элемент [math]memo[j][/math]. Найдем, сколько раз условие [math](1)[/math] в ходе выполнения программы является ложным при обращении к элементу [math]memo[j][/math]. Найдем в дереве такой узел, в котором есть обращение к [math]memo[j][/math], а в его поддереве обращений к этому элементу нет, причем [math]memo[j] = -1[/math]. До этого момента количество обращений к [math]memo[j][/math] не превышает глубины найденного узла, что не превосходит высоты дерева, что не превосходит некоторого полинома [math]p'(n)[/math]. После этого момента условие [math](1)[/math] будет принимать истинное значение при обращении к [math]memo[j][/math]. Значит, в ходе выполнения программы условие [math](1)[/math] является ложным при обращении к [math]memo[j][/math] не более [math]p'(n)[/math] раз. Так как всего в [math]memo[/math] не более [math]r(n)[/math] элементов, то суммарно за все время выполнения программы условие [math](1)[/math] принимает ложное значение не более [math]p''(n) = r(n) \cdot p'(n)[/math] раз, то есть [math]p''[/math] — полином. Отсюда следует, что присваивание [math](2)[/math] выполняется не более [math]p''(n)[/math] раз, а значит в дереве не более [math]p''(n)[/math] внутренних вершин. Значит всего в дереве не более [math]2 \cdot p''(n) + 1[/math] вершин, то есть данная программа работает за полиномиальное время. Итого, данная программа разрешает [math]\mathrm{TAUT}[/math] за полиномиальное время. А так как [math]\mathrm{TAUT} \in \mathrm{coNPC}[/math], то [math]\mathrm{P}=\mathrm{coNP}[/math], то есть [math]\mathrm{coP}=\mathrm{coNP}[/math], откуда [math]\mathrm{P}=\mathrm{NP}[/math].

[math]\triangleleft[/math]

См. также

• Класс P
• Классы NP и Σ₁