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

Материал из Викиконспекты
Перейти к: навигация, поиск
Лемма (1):
[math]L \in coNPC \Leftrightarrow \overline L \in NPC[/math]
Доказательство:
[math]\triangleright[/math]

Пусть [math]L \in coNPC[/math]. Тогда [math]L \in coNP[/math] и [math]\overline L \in NP[/math].

Рассмотрим произвольный язык [math]L_1 \in NP[/math]. Тогда [math]\overline {L_1} \in coNP[/math]. Так как [math]L \in coNPC[/math], то [math]\overline {L_1} \le L[/math], следовательно [math]L_1 \le \overline L[/math].

Получили, что [math]\overline L \in NP[/math] и [math]\forall L_1 \in NP \, L_1 \le \overline L[/math]. Значит [math]\overline L \in NPC[/math].

В обратную сторону доказательство аналогично.
[math]\triangleleft[/math]


Определение:
[math]TAUT = \{\phi[/math] — булева формула [math]| \forall x \, \phi(x)=1\}[/math].


Лемма (2):
[math]TAUT \in coNPC[/math]
Доказательство:
[math]\triangleright[/math]
[math]\overline {TAUT} = \{\phi | \exists x : \phi(x) \ne 1\} = \{\phi | \overline {\phi} \in SAT\}[/math], то есть [math]\overline {TAUT} \in NPC[/math]. Тогда по лемме (1) [math]TAUT \in coNPC[/math].
[math]\triangleleft[/math]


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


Теорема (Махэни, light):
[math]coNPC \cap SPARSE = \varnothing \Rightarrow P = NP[/math]
Доказательство:
[math]\triangleright[/math]

Пусть существует [math]S \in coNPC \cap SPARSE[/math]. Разрешим [math]TAUT[/math] за полином.

Для начала напишем программу, разрешающую [math]TAUT[/math]:

[math]check(\phi, i)[/math]
    if [math]memo[\phi] \ne -1[/math]
        return [math]memo[\phi][/math]
    if [math]\phi=0[/math]
        return 0
    if [math]\phi=1[/math]
        return 1
    [math]memo[\phi] \leftarrow check(\phi|_{x_i=0}, i+1)\, \&\&\, check(\phi|_{x_i=1}, i+1)[/math]
    return [math]memo[\phi][/math]     

Ответом будет [math]check(\phi, 1)[/math].

Так как [math]TAUT \in coNPC[/math] и [math]S \in coNPC[/math], то [math]TAUT \le_f S[/math], то есть [math]\phi \in TAUT \Leftrightarrow f(\phi) \in S[/math]. Поэтому, если в предыдущей программе заменить все обращения к [math]memo[\phi][/math], на [math]memo[f(\phi)][/math], то полученная программа по прежнему будет разрешать [math]TAUT[/math].

Оценим необходимый размер [math]memo[/math]. Можно считать, что [math]T(f(\phi)) \le q(n)[/math], где [math]n = |\phi|[/math], а [math]q[/math] — монотонно возрастающий полином. Тогда [math]|f(\phi)| \le q(n)[/math]. Так как [math]S \in SPARSE[/math], то [math]|S \cap \Sigma^k| \le p(k)[/math], где [math]p[/math] — полином. Можно считать, что [math]p[/math] монотонно возрастает. Тогда размер [math]memo[/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]memo[f(\phi)] \ne -1[/math]        //(1)
        return [math]memo[f(\phi)][/math]
    if [math]\phi=0[/math]
        return 0
    if [math]\phi=1[/math]
        return 1
    [math]memo[f(\phi)] \leftarrow check(\phi|_{x_i=0}, i+1)\, \&\&\, 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]

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

Рассмотрим произвольный элемент [math]memo[i][/math]. Заметим, что условие [math](1)[/math] в ходе выполнения программы является ложным при обращении к элементу [math]memo[i][/math] не более одного раза. Так как всего в [math]memo[/math] не более [math]r(n)[/math] элементов, то суммарно за все время выполнения программы условие [math](1)[/math] принимает ложное значение не более [math]r(n)[/math] раз. Отсюда следует, что присваивание [math](2)[/math] выполняется не более [math]r(n)[/math] раз, а значит в дереве не более [math]r(n)[/math] внутренних вершин. Значит всего в дереве не более [math]2 \cdot r(n) + 1[/math] вершин, то есть данная программа работает за полиномиальное время.

Итого, данная программа разрешает [math]TAUT[/math] за полиномиальное время. А так как [math]TAUT \in coNPC[/math], то [math]P=coNP[/math], то есть [math]coP=coNP[/math], откуда [math]P=NP[/math].
[math]\triangleleft[/math]