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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 32: Строка 32:
 
|proof=Пусть существует <tex>S \in coNPC \cap SPARSE</tex>. Решим <tex>TAUT</tex> за полином.
 
|proof=Пусть существует <tex>S \in coNPC \cap SPARSE</tex>. Решим <tex>TAUT</tex> за полином.
 
  <tex>check(\phi, i)</tex>
 
  <tex>check(\phi, i)</tex>
    '''if''' <tex>(memo[\phi] \ne -1)</tex>
 
        '''return''' <tex>memo[\phi]</tex>
 
 
     '''if''' <tex>\phi=0</tex>
 
     '''if''' <tex>\phi=0</tex>
 
         '''return''' 0
 
         '''return''' 0
Строка 39: Строка 37:
 
         '''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)\, \&\&\, check(\phi|_{x_i=1}, i+1)</tex>
 +
    '''return''' <tex>memo[\phi]</tex>
 
      
 
      
 +
blablabla
 +
 +
<tex>check(\phi, i)</tex>
 +
    '''if''' <tex>memo[f(\phi)] \ne -1</tex>
 +
        '''return''' <tex>memo[f(\phi)]</tex>
 +
    '''if''' <tex>\phi=0</tex>
 +
        '''return''' 0
 +
    '''if''' <tex>\phi=1</tex>
 +
        '''return''' 1
 +
    <tex>memo[f(\phi)] \leftarrow check(\phi|_{x_i=0}, i+1)\, \&\&\, check(\phi|_{x_i=1}, i+1)</tex>
 +
    '''if''' <tex>memo.size() > r(n)</tex>
 +
        '''exit''' <tex>0</tex>
 +
    '''return''' <tex>memo[f(\phi)]</tex>
 +
 
blablabla
 
blablabla
 
}}
 
}}

Версия 19:02, 13 апреля 2012

Лемма (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_f L[/math], следовательно [math]L_1 \le_f \overline L[/math].

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

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


Определение:
[math]TAUT = \{\phi | \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]check(\phi, i)[/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]
    

blablabla

[math]check(\phi, i)[/math]
    if [math]memo[f(\phi)] \ne -1[/math]
        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]
    if [math]memo.size() \gt  r(n)[/math]
        exit [math]0[/math]
    return [math]memo[f(\phi)][/math]
blablabla
[math]\triangleleft[/math]