Теорема Бермана — Форчуна — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(БЕСИТЕ вы меня)
Строка 1: Строка 1:
 
{{Лемма
 
{{Лемма
 
|about=1
 
|about=1
|statement=<tex>L \in \mathrm{coNPC} \Leftrightarrow \overline L \in \mathrm{NPC}</tex>
+
|statement=<tex>L \in \mathrm{coNPC} \Leftrightarrow \overline L \in \mathrm{NPC}</tex>.
 
|proof=Пусть <tex>L \in \mathrm{coNPC}</tex>. Тогда <tex>L \in \mathrm{coNP}</tex> и <tex>\overline L \in \mathrm{NP}</tex>.
 
|proof=Пусть <tex>L \in \mathrm{coNPC}</tex>. Тогда <tex>L \in \mathrm{coNP}</tex> и <tex>\overline L \in \mathrm{NP}</tex>.
  
Строка 12: Строка 12:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<tex>TAUT = \{\phi</tex> {{---}} булева формула <tex>| \forall x = (x_1, x_2, \ldots , x_m) \, \phi(x)=1\}</tex>.
+
<tex>\mathrm{TAUT} = \{\phi</tex> {{---}} булева формула <tex>| \forall x = (x_1, x_2, \ldots , x_m) \, \phi(x)=1\}</tex>.
 
}}
 
}}
  
 
{{Лемма
 
{{Лемма
 
|about=2
 
|about=2
|statement=<tex>TAUT \in \mathrm{coNPC}</tex>
+
|statement=<tex>\mathrm{TAUT} \in \mathrm{coNPC}</tex>.
|proof=<tex>\overline {TAUT} = \{\phi | \exists x : \phi(x) \ne 1\} = \{\phi | \overline {\phi} \in SAT\}</tex>, то есть <tex>\overline {TAUT} \in \mathrm{NPC}</tex>. Тогда по лемме (1) <tex>TAUT \in \mathrm{coNPC}</tex>.
+
|proof=<tex>\overline {\mathrm{TAUT}} = \{\phi | \exists x : \phi(x) \ne 1\} = \{\phi | \overline {\phi} \in SAT\}</tex>, то есть <tex>\overline {\mathrm{TAUT}} \in \mathrm{NPC}</tex>. Тогда по лемме (1) <tex>\mathrm{TAUT} \in \mathrm{coNPC}</tex>.
 
}}
 
}}
  
Строка 27: Строка 27:
  
 
{{Теорема
 
{{Теорема
|statement=<tex>\mathrm{coNPC} \cap \mathrm{SPARSE} \ne \varnothing \Rightarrow \mathrm{P} = \mathrm{NP}</tex>
+
|statement=<tex>\mathrm{coNPC} \cap \mathrm{SPARSE} \ne \varnothing \Rightarrow \mathrm{P} = \mathrm{NP}</tex>.
|proof=Пусть существует <tex>S \in \mathrm{coNPC} \cap \mathrm{SPARSE}</tex>. Разрешим <tex>TAUT</tex> за полином.
+
|author=Берман, Форчун
 +
|proof=Пусть существует <tex>S \in \mathrm{coNPC} \cap \mathrm{SPARSE}</tex>. Разрешим <tex>\mathrm{TAUT}</tex> за полином.
  
Для начала напишем программу, разрешающую <tex>TAUT</tex>:
+
Для начала напишем программу, разрешающую <tex>\mathrm{TAUT}</tex>:
  <tex>check(\phi, i)</tex>
+
  <tex>check(\phi, i)</tex>:
 
     '''if''' <tex>memo[\phi] \ne -1</tex>
 
     '''if''' <tex>memo[\phi] \ne -1</tex>
 
         '''return''' <tex>memo[\phi]</tex>
 
         '''return''' <tex>memo[\phi]</tex>
Строка 38: Строка 39:
 
     '''if''' <tex>\phi=1</tex>
 
     '''if''' <tex>\phi=1</tex>
 
         '''return''' 1
 
         '''return''' 1
     <tex>memo[\phi] \leftarrow check(\phi|_{x_i=0}, i+1)\, \&\&\, check(\phi|_{x_i=1}, i+1)</tex>
+
     <tex>memo[\phi] \leftarrow check(\phi|_{x_i=0}, i+1) \wedge check(\phi|_{x_i=1}, i+1)</tex>
 
     '''return''' <tex>memo[\phi]</tex>     
 
     '''return''' <tex>memo[\phi]</tex>     
 
Ответом будет <tex>check(\phi, 1)</tex>.
 
Ответом будет <tex>check(\phi, 1)</tex>.
  
Так как <tex>TAUT \in \mathrm{coNPC}</tex> и <tex>S \in \mathrm{coNPC}</tex>, то <tex>TAUT \le S</tex>, то есть <tex>\exists f \in \widetilde{P} : \phi \in TAUT \Leftrightarrow f(\phi) \in S</tex>. Поэтому, если в предыдущей программе заменить все обращения к <tex>memo[\phi]</tex>, на <tex>memo[f(\phi)]</tex>, то полученная программа по-прежнему будет разрешать <tex>TAUT</tex>.
+
Так как <tex>\mathrm{TAUT} \in \mathrm{coNPC}</tex> и <tex>S \in \mathrm{coNPC}</tex>, то <tex>\mathrm{TAUT} \le S</tex>, то есть <tex>\exists f \in \mathrm{\widetilde{P}} : \phi \in \mathrm{TAUT} \Leftrightarrow f(\phi) \in S</tex>. Поэтому, если в предыдущей программе заменить все обращения к <tex>memo[\phi]</tex>, на <tex>memo[f(\phi)]</tex>, то полученная программа по-прежнему будет разрешать <tex>\mathrm{TAUT}</tex>.
  
Оценим необходимый размер <tex>memo</tex>. Можно считать, что <tex>T(f(\phi)) \le q(n)</tex>, где <tex>n = |\phi|</tex>, а <tex>q</tex> {{---}} монотонно возрастающий полином. Тогда <tex>|f(\phi)| \le q(n)</tex>. Так как <tex>S \in \mathrm{SPARSE}</tex>, то <tex>|S \cap \Sigma^k| \le p(k)</tex>, где <tex>p</tex> {{---}} полином. Можно считать, что <tex>p</tex> монотонно возрастает. Тогда размер <tex>memo</tex> можно оценить сверху: <tex>memo.size() \le \sum\limits_{i=0}^{q(n)}p(i) \le (1+q(n)) \cdot p(q(n)) \le r(n)</tex>, где <tex>r(n)</tex> {{---}} полином.
+
Оценим необходимый размер <tex>memo</tex>. Можно считать, что <tex>\mathrm{T}(f, \phi) \le q(n)</tex>, где <tex>n = |\phi|</tex>, а <tex>q</tex> {{---}} монотонно возрастающий полином. Тогда <tex>|f(\phi)| \le q(n)</tex>. Так как <tex>S \in \mathrm{SPARSE}</tex>, то <tex>|S \cap \Sigma^k| \le p(k)</tex>, где <tex>p</tex> {{---}} полином. Можно считать, что <tex>p</tex> монотонно возрастает. Тогда размер <tex>memo</tex> можно оценить сверху: <tex>memo.size() \le \sum\limits_{i=0}^{q(n)}p(i) \le (1+q(n)) \cdot p(q(n)) \le r(n)</tex>, где <tex>r(n)</tex> {{---}} полином.
  <tex>check(\phi, i)</tex>
+
  <tex>check(\phi, i)</tex>:
 
     '''if''' <tex>memo[f(\phi)] \ne -1</tex>        //(1)
 
     '''if''' <tex>memo[f(\phi)] \ne -1</tex>        //(1)
 
         '''return''' <tex>memo[f(\phi)]</tex>
 
         '''return''' <tex>memo[f(\phi)]</tex>
Строка 52: Строка 53:
 
     '''if''' <tex>\phi=1</tex>
 
     '''if''' <tex>\phi=1</tex>
 
         '''return''' 1
 
         '''return''' 1
     <tex>memo[f(\phi)] \leftarrow check(\phi|_{x_i=0}, i+1)\, \&\&\, check(\phi|_{x_i=1}, i+1)</tex>        //(2)
+
     <tex>memo[f(\phi)] \leftarrow check(\phi|_{x_i=0}, i+1) \wedge check(\phi|_{x_i=1}, i+1)</tex>        //(2)
 
     '''if''' <tex>memo.size() > r(n)</tex>
 
     '''if''' <tex>memo.size() > r(n)</tex>
 
         '''exit''' <tex>0</tex>
 
         '''exit''' <tex>0</tex>
Строка 60: Строка 61:
 
Рассмотрим произвольный элемент <tex>memo[i]</tex>. Заметим, что условие <tex>(1)</tex> в ходе выполнения программы является ложным при обращении к элементу <tex>memo[i]</tex> не более одного раза. Так как всего в <tex>memo</tex> не более <tex>r(n)</tex> элементов, то суммарно за все время выполнения программы условие <tex>(1)</tex> принимает ложное значение не более <tex>r(n)</tex> раз. Отсюда следует, что присваивание <tex>(2)</tex> выполняется не более <tex>r(n)</tex> раз, а значит в дереве не более <tex>r(n)</tex> внутренних вершин. Значит всего в дереве не более <tex>2 \cdot r(n) + 1</tex> вершин, то есть данная программа работает за полиномиальное время.
 
Рассмотрим произвольный элемент <tex>memo[i]</tex>. Заметим, что условие <tex>(1)</tex> в ходе выполнения программы является ложным при обращении к элементу <tex>memo[i]</tex> не более одного раза. Так как всего в <tex>memo</tex> не более <tex>r(n)</tex> элементов, то суммарно за все время выполнения программы условие <tex>(1)</tex> принимает ложное значение не более <tex>r(n)</tex> раз. Отсюда следует, что присваивание <tex>(2)</tex> выполняется не более <tex>r(n)</tex> раз, а значит в дереве не более <tex>r(n)</tex> внутренних вершин. Значит всего в дереве не более <tex>2 \cdot r(n) + 1</tex> вершин, то есть данная программа работает за полиномиальное время.
  
Итого, данная программа разрешает <tex>TAUT</tex> за полиномиальное время. А так как <tex>TAUT \in \mathrm{coNPC}</tex>, то <tex>\mathrm{P}=\mathrm{coNP}</tex>, то есть <tex>\mathrm{coP}=\mathrm{coNP}</tex>, откуда <tex>\mathrm{P}=\mathrm{NP}</tex>.
+
Итого, данная программа разрешает <tex>\mathrm{TAUT}</tex> за полиномиальное время. А так как <tex>\mathrm{TAUT} \in \mathrm{coNPC}</tex>, то <tex>\mathrm{P}=\mathrm{coNP}</tex>, то есть <tex>\mathrm{coP}=\mathrm{coNP}</tex>, откуда <tex>\mathrm{P}=\mathrm{NP}</tex>.
 
}}
 
}}
  

Версия 00:16, 3 июня 2012

Лемма (1):
[math]L \in \mathrm{coNPC} \Leftrightarrow \overline L \in \mathrm{NPC}[/math].
Доказательство:
[math]\triangleright[/math]

Пусть [math]L \in \mathrm{coNPC}[/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 \in \mathrm{coNPC}[/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]| \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 | \exists x : \phi(x) \ne 1\} = \{\phi | \overline {\phi} \in SAT\}[/math], то есть [math]\overline {\mathrm{TAUT}} \in \mathrm{NPC}[/math]. Тогда по лемме (1) [math]\mathrm{TAUT} \in \mathrm{coNPC}[/math].
[math]\triangleleft[/math]


Определение:
[math]\mathrm{SPARSE} = \{L | \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]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) \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]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) \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]

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

Рассмотрим произвольный элемент [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]\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]

См. также