171
правка
Изменения
м
Добавил некоторые ссылки
'''Теорема Ладнера''' (Ladner's Theorem) утверждает, что если [[Класс P|P]] не совпадает с [[Класс NP|NP]], то существует язык, принадлежащий <tex>\mathrm{NP}</tex>, но не являющийся ни полиномиальным, ни [[NP-полнота|NP-полным]].
{{Теорема
<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{[[Примеры NP-полных_языков. Теорема_Кука#NP-полнота_2|SAT}</tex>]]) нельзя [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|свести по Карпу ]] к полиномиальному. Будем искать такой язык <tex>A</tex>, чтобы язык <tex>L = \mathrm{SAT} \cap A</tex> удовлетворял следующим условиям:
# <tex>L \in \mathrm{NP}</tex> (для этого достаточно, чтобы выполнялось <tex>A \in \mathrm{P}</tex>);
