Теорема Ладнера — различия между версиями
Shevchen (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 2 промежуточные версии 2 участников) | |||
Строка 79: | Строка 79: | ||
for <tex>x</tex> : <tex>|x| \le \log_2 n, |f_i(x)| \le \log_2 n</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(|x|) \equiv 1 \pmod{2}</tex> or <tex>f_i(x) \not \in \mathrm{SAT}]</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> | <tex>g(n+1) := g(n)+1</tex> | ||
return | return | ||
− | if <tex>x \not \in \mathrm{SAT}</tex> and <tex>[g(|x|) \equiv 0 \pmod{2}</tex> and <tex>f_i(x) \in \mathrm{SAT}]</tex> | + | 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> | <tex>g(n+1) := g(n)+1</tex> | ||
return | return |
Текущая версия на 19:35, 4 сентября 2022
Теорема Ладнера (Ladner's Theorem) утверждает, что если P не совпадает с NP, то существует язык, принадлежащий , но не являющийся ни полиномиальным, ни NP-полным.
Иллюстрация
Определим язык
как множество таких формул , что чётно. Иными словами, — это язык формул с длинами, лежащими в промежутках Далее будем обозначать как .Рассмотрим язык SAT всех удовлетворимых формул. Логично предположить, что как в , так и в лежит бесконечное множество элементов из , не распознаваемых за полиномиальное время, поэтому . Из и следует, что .
Осталось показать, что сводящая по Карпу к .
не является NP-полным. Пусть это не так. Тогда из NP-полноты следует, что существует полиномиальная функция ,Возьмём формулу
длиной . Она не лежит в и, следовательно, в . Функция не может перевести в промежуток или дальше, так как размер выхода полиномиальной функции не может быть экспоненциально больше длины входа. Значит, отображается в меньший промежуток, но в этом случае размер выхода экспоненциально меньше длины входа. Добавляя к этому то, что проверку на принадлежность к можно осуществить за (это следует из её принадлежности классу ), получаем программу, разрешающую за полином. Утверждение о том, что все формулы длиной принадлежат классу , скорее всего неверно, и, следовательно, язык не является NP-полным.Заметим, что это объяснение не является доказательством!
Теорема
Теорема (Ладнер): |
. |
Доказательство: |
Предположим, что SAT) нельзя свести по Карпу к полиномиальному. Будем искать такой язык , чтобы язык удовлетворял следующим условиям: . Из этого следует, что никакой -полный язык (например,
Если выполнены все три свойства, то .Пусть — все машины Тьюринга из (возможно, с повторениями), расположенные в таком порядке, чтобы для любого .Пусть — аналогичное множество полиномиальных функций: для любого .Для простоты будем считать, что . Построим такую неубывающую функцию , что при для выполняются три перечисленных свойства.Алгоритм построения gПоложим . Для построим рекурсивно — с помощью .
for: if and or return if and and return
for: if and or return if and and return Корректность алгоритмаПроверим выполнение второго и третьего свойств языка .
Таким образом, при верности предположения второе и третье свойства выполнены.Время работы алгоритмаПроверим выполнение первого свойства языка . Для этого достаточно установить полиномиальность . Покажем, что отличается от не более, чем на неубывающий полином . Из этого будет следовать полиномиальность : .Заметим, что по построению для .Вычисление значения состоит из вычисления , проверки неравенства и, возможно, запуска одной из двух внутренних функций, время выполнения которых составляет:
Вычислить можно за .Таким образом, .Пусть Тогда, в силу . Существует константа , для которой при любом верно . и неравенства строкой выше, по индукции легко доказать, что ограничено сверху , то есть , а, в свою очередь, . |
Источник
- William Gasarch, Lance Fortnow. Two Proofs of Ladner’s Theorem