171
правка
Изменения
м
Подправил формулы
|author=Ладнер
|statement=
<tex>\mathrm{P} \neq \mathrm{NP} \Rightarrow \mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC}) \neq \emptysetvarnothing</tex>
|proof=
Предположим, что <tex>\mathrm{P} \neq \mathrm{NP}</tex>. Из этого следует, что никакой <tex>\mathrm{NP}</tex>-полный язык (например, [[Примеры NP-полных_языков. Теорема_Кука#NP-полнота_2|SAT]]) нельзя [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|свести по Карпу]] к полиномиальному. Будем искать такой язык <tex>A</tex>, чтобы язык <tex>L = \mathrm{SAT} \cap A</tex> удовлетворял следующим условиям:
Пусть <tex>f_1, \ldots, f_n, \ldots</tex> — аналогичное множество полиномиальных функций: <tex>T(f_i(x)) \le |x|^i</tex> для любого <tex>x \in \Sigma^*</tex>.
Для простоты будем считать, что <tex>|\Sigma| = 2</tex>. Построим такую ''неубывающую'' функцию <tex>g \in \tilde{\mathrm{P}}</tex>, что для <tex>A = \{x \in \Sigma^*: g(|x|) \% equiv 0 \pmod{2 = 0} \}</tex> выполняются три названных свойства.
=== Построение <tex>g</tex> ===
* <tex>g(n) = 2i</tex>.
for <tex>x</tex> : <tex>|x| \le \log_2 n</tex>
if <tex>M_i(x)</tex> and (<tex>[g(|x|) \% equiv 1 \pmod{2 = 1}</tex> or <tex>x \not \in \mathrm{SAT})]</tex>
<tex>g(n+1) := g(n)+1</tex>
return
if <tex>! M_i(x)</tex> and (<tex>[g(|x|) \% equiv 0 \pmod{2 = 0}</tex> and <tex>x \in \mathrm{SAT})]</tex>
<tex>g(n+1) := g(n)+1</tex>
return
* <tex>g(n) = 2i + 1</tex>.
for <tex>x</tex> : <tex>|x| \le \log_2 n, |f_i(x)| \le \log_2 n</tex>
if <tex>x \in \mathrm{SAT}</tex> and (<tex>[g(|f_i(x)|) \% equiv 1 \pmod{2 = 1}</tex> or <tex>f_i(x) \not \in \mathrm{SAT})]</tex> <tex>g(n+1) := g(n)+1</tex>, return if <tex>x \not \in \mathrm{SAT}</tex> and (<tex>[g(|f_i(x)|) \% equiv 0 \pmod{2 = 0}</tex> and <tex>f_i(x) \in \mathrm{SAT})]</tex> <tex>g(n+1) := g(n)+1</tex>, return
<tex>g(n+1) := g(n)</tex>
* Пусть <tex>g(n)</tex> не имеет предела при <tex>n \to \infty</tex>. Значит, для любой <tex>M_i</tex> в <tex>L</tex> существует элемент, на котором <tex>M_i</tex> «ошибается»; аналогично, для любой полиномиальной функции <tex>f_i</tex> существует элемент, на котором <tex>f_i</tex> неверно сводит <tex>\mathrm{SAT}</tex> к <tex>L</tex>. Оба свойства выполнены.
* Пусть <tex>\lim\limits_{n \to \infty} g(n) = 2i</tex>. Значит, в нашем множестве существует такая машина Тьюринга <tex>M_i</tex>, распознающая <tex>L</tex>, что <tex>\forall x \Rightarrow M_i(x) = [g(|x|) \% equiv 0 \pmod{2 = 0 } \wedge x \in \mathrm{SAT})]</tex>. С одной стороны, <tex>M_i</tex> работает за полином, и <tex>L \in \mathrm{P}</tex>. С другой стороны, по определению <tex>A</tex>, <tex>L</tex> различается с <tex>\mathrm{SAT}</tex> в конечном числе элементов, значит <tex>\mathrm{SAT} \le L</tex>. Получено противоречие с предположением <tex>\mathrm{P} \neq \mathrm{NP}</tex>.
* Пусть <tex>\lim\limits_{n \to \infty} g(n) = 2i + 1</tex>. Тогда в нашем множестве полиномиальных функций существует <tex>f_i : \forall x \Rightarrow [x \in SAT] = [g(|f_i(x)|) \% equiv 0 \pmod{2 = 0 } \wedge f_i(x) \in \mathrm{SAT}]</tex>. С одной стороны, <tex>\mathrm{SAT} \le L</tex> с помощью <tex>f_i</tex>. С другой стороны, из определения <tex>A</tex> выходит, что язык <tex>L</tex> конечен, значит <tex>L \in \mathrm{P}</tex>. Снова получено противоречие с предположением.
Таким образом, при верности предположения <tex>\mathrm{P} \neq \mathrm{NP}</tex> второе и третье свойства <tex>L</tex> выполнены.
