70
правок
Изменения
Нет описания правки
{{Лемма
|about=1
|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>.
Рассмотрим произвольный язык <tex>L_1 \in \mathrm{NP}</tex>. Тогда <tex>\overline {L_1} \in \mathrm{coNP}</tex>. Так как <tex>L \in \mathrm{coNPC}</tex>, то <tex>\overline {L_1} \le L</tex>, следовательно <tex>L_1 \le \overline L</tex> (по [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи#Свойства сведения|лемме]]).
Получили, что <tex>\overline L \in \mathrm{NP}</tex> и <tex>\forall L_1 \in \mathrm{NP } \Rightarrow L_1 \le \overline L</tex>. Значит <tex>\overline L \in \mathrm{NPC}</tex>.
В обратную сторону доказательство аналогично.
}}
{{Лемма
|about=2
|statement=<tex>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>.
}}
{{Определение
|definition=
<tex>\mathrm{SPARSE } = \{L | \exists</tex> полином <tex>p: \forall n \, |L \cap \Sigma^n| \le p(n)\}</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> за полином.
Для начала напишем программу, разрешающую <tex>TAUT</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>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>check(\phi, i)</tex>
'''if''' <tex>memo[f(\phi)] \ne -1</tex> //(1)
Рассмотрим произвольный элемент <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>.
}}
[[Категория: Теория сложности]]
