Изменения

Определим Рассмотрим язык [[SAT]] всех удовлетворимых формул. Логично предположить, что как в <mathtex>A</mathtex> как множество таких формул ,так и в <mathtex>\alphabar{A}</mathtex>,что лежит бесконечное множество элементов из <mathtex>\left\lfloor \fracmathrm{1SAT}{2}\log_{10}^*|\alpha|\right\rfloor</mathtex> чётно. Иными словами,<math>A</math> — это язык формул с длинамине распознаваемых за полиномиальное время, лежащими в промежутках поэтому <mathtex>\left[1,10^mathrm{10SAT}\right),cap A \left[not\underbrace{10^{10^{\cdot^{in \cdot^mathrm{10P}}}}}_4, \underbrace{10^{10^{</tex>.Из <tex>A \cdot^{in \cdot^mathrm{10}}}P}}_6\right), \dots</mathtex>Далее будем обозначать и <mathtex>\underbrace{a^{a^mathrm{SAT} \cdot^{in \cdot^mathrm{a}}}NP}}_n</mathtex> как следует, что <mathtex>^\mathrm{SAT} \cap A \in \mathrm{nNP}a</mathtex>.

Рассмотрим язык Осталось показать, что <mathtex>\mathrm{SAT} \cap A</mathtex>не является NP-полным. Пустьэто не так. Логично предположитьТогда из NP-полноты следует, что как в существует полиномиальная функция <math>Af</math>,так и в [[Сведение по Карпу|сводящая по Карпу]] <mathtex>\barmathrm{ASAT}</mathtex> лежит бесконечное множество элементов из к <mathtex>SAT</math>.Из <math>A \in P</math> и <math>SAT \in NP</math> следует, что <math>mathrm{SAT } \cap A \in NP</mathtex>.

ПредположимВозьмём формулу <tex>\varphi</tex> длиной <tex>^{2k+1}10</tex>. Она не лежит в <tex>A</tex> и, что следовательно, в <mathtex>\mathrm{SAT } \cap A</mathtex> является NP-полным.Из NP-полноты следуетФункция <tex>f</tex> не может перевести <tex>\varphi</tex> в промежуток<tex>\left[^{2k+2}10, ^{2k+4}10\right)</tex> или дальше, так как размервыхода полиномиальной функции не может быть экспоненциально больше длинывхода. Значит, <tex>\varphi</tex> отображается в меньший промежуток, нов этом случае размер выхода экспоненциально меньше длины входа. Добавляяк этому то, что существует полиномиальная функция проверку на принадлежность <tex>f сводящая по Карпу (\varphi)<math/tex>к<tex>\mathrm{SAT} \cap A</tex> можно осуществить за <tex>O(2^{poly})</tex>(это следует из её принадлежности классу <tex>\mathrm{NP}</tex>), получаем программу,разрешающую <tex>\varphi</mathtex> за полином. Утверждение о том, что все формулы<tex>\varphi</tex> длиной <tex>^{2k+1}10</tex> принадлежат классу<tex>\mathrm{P}</tex>, скорее всего неверно, и, следовательно, язык к <mathtex>\mathrm{SAT } \cap A</mathtex>не является NP-полным.

Возьмем формулу <math>\phi</math> длиной <math>^{2k+1}10</math>. Она не лежит в <math>A</math> и,следовательно, в <math>SAT \cap A</math>. Функция <math>f</math> не может перевести <math>\phi</math>в промежуток <math>\left[^{2k+2}10, ^{2k+4}10\right)</math> или дальше, так как размер выходаполиномиальной функции не может быть экспоненциально больше длинны входа. Значит <math>\phi</math>отображается в меньший промежуток, но в этом случае размер выхода экспоненциально меньше длины входа.Добавляя к этому тоЗаметим, что проверку на принадлежность <math>f(\phi)</math> <math>SAT \cap A</math> можно осуществитьза <math>O(2^{poly})</math> (это следует из принадлежности <math>NP</math>), получаем программу разрешающую <math>\phi</math> за полином, а это почему-то плохо.объяснение не является доказательством!

==ДоказательствоТеорема == {{Теорема|author=Ладнер|statement=<tex>\mathrm{P} \neq \mathrm{NP} \Rightarrow \mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC}) \neq \varnothing</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>L \in \mathrm{NP}</tex> (для этого достаточно, чтобы выполнялось <tex>A \in \mathrm{P}</tex>);# <tex>L \not \in \mathrm{P}</tex>;# <tex>\mathrm{SAT} \not \le L</tex>. Если выполнены все три свойства, то <tex>L \in \mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC})</tex>. Пусть <tex>M_1, \ldots, M_n, \ldots</tex> — все машины Тьюринга из <tex>\tilde{\mathrm{P}}</tex> (возможно, с повторениями), расположенные в таком порядке, чтобы <tex>T(M_i, x) \le |x|^i</tex> для любого <tex>x \in \Sigma^*</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} \}</tex> для <tex>L</tex> выполняются три перечисленных свойства. === Алгоритм построения g === Положим <tex>g(0) = g(1) = 1</tex>. Для <tex>n \ge 1</tex> построим <tex>g(n + 1)</tex> рекурсивно — с помощью <tex>g(0), g(1), \ldots, g(n)</tex>. * Если <tex>(\log_2 n)^{g(n)} \ge n</tex>, то <tex>g(n+1) := g(n)</tex>. Иначе выполняем один из следующих пунктов. * Пусть вычисленное значение <tex>g(n) = 2 i</tex>. Определим <tex>g(n+1)</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}</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}</tex> and <tex>x \in \mathrm{SAT}]</tex> <tex>g(n+1) := g(n)+1</tex> return <tex>g(n+1) := g(n)</tex> * Пусть вычисленное значение <tex>g(n) = 2 i - 1</tex>. Определим <tex>g(n+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}</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}</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>L = \mathrm{SAT} \cap A</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} \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} \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> выполнены. === Время работы алгоритма === Проверим выполнение первого свойства языка <tex>L</tex>. Для этого достаточно установить полиномиальность <tex>A</tex>. Покажем, что <tex>T(g, n)</tex> отличается от <tex>T(g, n - 1)</tex> не более, чем на неубывающий полином <tex>p(n)</tex>. Из этого будет следовать полиномиальность <tex>g</tex>: <tex>T(g, n) \le p(n) + p(n - 1) + \ldots + p(1) \le n p(n) \in poly(n)</tex>. Заметим, что <tex>g(n) \le n</tex> по построению для <tex>n \ge 1</tex>. Вычисление значения <tex>g(n+1)</tex> состоит из вычисления <tex>g(n)</tex>, проверки неравенства <tex>(\log_2 n)^{g(n)} \ge n</tex> и, возможно, запуска одной из двух внутренних функций, время выполнения которых составляет: <ul><li>для случая <tex>g(n) = 2 i</tex>:<br/><tex>\parbox{0px}{\begin{align*}T(n) & \le 2^{\log_2 n} (T(M_i, x) + T(g, |x|) + T(x \in \mathrm{SAT})) \le \\ & \le k_1 n (|x|^i + T(g, |x|) + 2^{|x|}|x|) \le \\ & \le k_1 n ((\log_2 n)^{g(n)} + T(g, \log_2 n) + 2^{\log_2 n} \log_2 n) \le \\ & \le k_1 (n^2 + n^2 \log_2 n + n T(g, \log_2 n)) \le \\ & \le k_1 (2n^3 + n T(g, \log_2 n));\end{align*}}</tex></li> <li>для случая <tex>g(n) = 2 i - 1</tex>:<br/><tex>\parbox{0px}{\begin{align*}T(n) & \le 2^{\log_2 n} (T(x \in \mathrm{SAT}) + T(g, |f_i(x)|) + T(f_i(x) \in \mathrm{SAT})) \le \\ & \le k_2 n (2^{\log_2 n} \log_2 n + T(g, \log_2 n) + 2^{\log_2 n} \log_2 n) \le \\ & \le k_2 (2n^2 \log_2 n + n T(g, \log_2 n)) \le \\ & \le k_2 (2n^3 + n T(g, \log_2 n)).\end{align*}}</tex></li></ul> Вычислить <tex>(\log_2 n)^{g(n)}</tex> можно за<tex>k_3 \log_2 g(n) |(\log_2 n)^{g(n)}|^2 \le k_3 (g(n) |log_2 n|)^2 log_2 n \le k_3 n^3</tex>. Таким образом,<tex>T(g, n) \le T(g, n-1) + k (n^3 + n T(g, \log_2 n))</tex>. Пусть <tex>T(g, 1) = d</tex>. Существует константа <tex>c \ge d</tex>, для которой при любом <tex>n</tex> верно<tex>c (n-1)^4 + k n^3 + k n c (\log_2 n)^4 \le c n^4</tex>. Тогда, в силу <tex>T(g, 1) = d \le c \cdot 1^4</tex> и неравенства строкой выше, по индукции легко доказать, что <tex>T(g, n)</tex> ограничено сверху <tex>c n^4</tex>, то есть <tex>g \in \tilde{\mathrm{P}}</tex>, а, в свою очередь, <tex>A \in \mathrm{P}</tex>.}} == Источник ==* ''William Gasarch, Lance Fortnow''. [http://blog.computationalcomplexity.org/media/ladner.pdf Two Proofs of Ladner’s Theorem] [[Категория: Теория сложности]]