109
правок
Изменения
м
__TOC__
добавил wiki-ссылки
'''Теорема Ладнера''' (Ladner's Theorem) утверждает,
что если <math>[[P \ne ]] не совпадает с [[NP</math>]], то существует язык <math>L</math>,принадлежащий <math>NP \setminus (P \cup NPC)</math>, но не являющийся полиномиальным и [[NP-полнота|NP-полным]].
==Иллюстрация==
как <math>^{n}a</math>.
Рассмотрим язык <math>[[SAT</math>]] всех удовлетворимых формул. Логично предположить, что как в <math>A</math>,
так и в <math>\bar{A}</math> лежит бесконечное множество элементов из <math>SAT</math>,
не распознаваемых за полиномиальное время, поэтому <math>SAT \cap A \not\in P</math>.
Осталось показать, что <math>SAT \cap A</math> не является NP-полным. Пусть
это не так. Тогда из NP-полноты следует, что существует полиномиальная функция <math>f</math>,
[[Сведение по Карпу|сводящая по Карпу ]] <math>SAT</math> к <math>SAT \cap A</math>.
Возьмём формулу <math>\varphi</math> длиной <math>^{2k+1}10</math>.
