171
правка
Изменения
м
Добавил шаблон «теорема»
'''Теорема Ладнера''' (Ladner's Theorem) утверждает, что если [[Класс P|P]] не совпадает с [[Класс NP|NP]], то существует язык, принадлежащий NP, но не являющийся ни полиномиальным, ни [[NP-полнота|NP-полным]].
{{Теорема|author=Ладнер|statement= Доказательство <tex>\mathrm{P} \neq \mathrm{NP} \Rightarrow \mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC}) \neq \emptyset</tex>|proof==
Предположим, что <tex>\mathrm{P} \neq \mathrm{NP}</tex>. Из этого следует, что никакой <tex>\mathrm{NP}</tex>-полный язык (например, <tex>\mathrm{SAT}</tex>) нельзя свести по Карпу к полиномиальному. Будем искать такой язык <tex>A</tex>, чтобы язык <tex>L = \mathrm{SAT} \cap A</tex> удовлетворял следующим условиям:
Тогда, в силу <tex>T^g(1) = d \le c 1^7</tex> и неравенства выше, по индукции легко доказать, что <tex>T^g(n)</tex> ограничено сверху <tex>c n^7</tex>, то есть <tex>g \in \tilde{\mathrm{P}}</tex>, а, в свою очередь, <tex>A \in \mathrm{P}</tex>.
}}
== Источник ==
