Обобщенная теорема Ладнера

45

Теорема Ладнера гласит, что если P ≠ NP, то существует бесконечная иерархия классов сложности, строго содержащих P и строго содержащихся в NP. В доказательстве используется полнота SAT при многократном сокращении NP. Иерархия содержит классы сложности, построенные по типу диагонализации, каждый из которых содержит некоторый язык, к которому языки в низших классах сводятся не много-один.

Это мотивирует мой вопрос:

Пусть C - класс сложности, а D - класс сложности, который строго содержит C. Если D содержит языки, полные для некоторого понятия редукции, существует ли бесконечная иерархия классов сложности между C и D по отношению к сокращение?

Более конкретно, я хотел бы знать, существуют ли результаты, известные для D = P и C = LOGCFL или C = NC , для соответствующего понятия сокращения.


Статья Ладнера уже включает теорему 7 для ограниченных в пространстве классов C, как указал Каве в ответе. В его самой сильной форме это говорит: если NL ≠ NP, то существует бесконечная последовательность языков между NL и NP, строго возрастающей жесткости. Это несколько более общий вариант, чем обычная версия (теорема 1), которая зависит от P ≠ NP. Однако в работе Ладнера рассматривается только D = NP.

Андраш Саламон
источник
1
Сначала можно задать вопрос, сосредоточившись на классах, которые, как мы уже знаем, различаются. Например, существует ли бесконечная иерархия между AC 0 и AC 0 [6] относительно проекций? Это выглядит как сложный вопрос! :-)00
Михаэль Кадилхак
См. Также cstheory.stackexchange.com/questions/52/… для вопроса об интервале от P до NP.
Андрас Саламон

Ответы:

33

Ответ на ваш вопрос «да» для широкого спектра классов и сокращений, включая сокращения пространства журналов и классов, которые вы упомянули, как это доказано в следующих статьях:

Х. Воллмер. Техника гэп-языка пересмотрена . Computer Science Logic, Конспект лекций в области компьютерных наук. 533, с. 389-399, 1990.

К. Риган и Х. Воллмер. Языки Gap-языков и классы сложности во время регистрации . Теоретическая информатика, 188 (1-2): 101-116, 1997.

(Вы можете скачать gzip-файлы постскриптума этих статей здесь .)

Доказательства следуют основному принципу расширения Уве Шенинга теоремы Ладнера:

Уве Шенинг Единый подход к получению диагональных множеств в классах сложности . Теоретическая информатика 18 (1): 95-103, 1982.

Доказательство Шенинга всегда было моим любимым доказательством теоремы Ладнера - оно простое и общее.

Джон Уотроус
источник
а как насчет обещания классов?
Маркос Вильягра
12

Вполне вероятно, что вы можете сделать это в общей обстановке. Почти наверняка такой результат уже был подтвержден в общих чертах, но ссылки избегают меня в данный момент. Итак, вот аргумент с нуля.

Рецензия на http://oldblog.computationalcomplexity.org/media/ladner.pdf содержит два доказательства теоремы Ладнера. Второе доказательство Рассела Импальяццо дает язык в форме { x 01 f ( | x | ) }, где x кодирует выполнимую формулу, а f является определенной вычислимой функцией за полиномиальное время. То есть, просто заполнив SAT соответствующим числом 1 , вы можете получить «NP-промежуточные» наборы. Заполнение выполняется для «диагонализации» всех возможных полиномиальных сокращений времени, так что нет полиномиального сокращения времени от SAT до L 1.L1x01f(|x|)xf1L1будет работать (при условии, что ). Чтобы доказать, что существует бесконечно много степеней твердости, нужно иметь возможность заменить L 1 вместо SAT в приведенном выше аргументе и повторить аргумент для L 2 = { x 0 1 f ( | x | ) | x L 1 }. Повторите с L i = { x 0 1 f ( | x | ) | x L i -PNPL1L2=Икс01е(|Икс|)|ИксL1Lязнак равно }Икс01е(|Икс|)|ИксLя-1

Кажется очевидным, что такое доказательство можно обобщить на классы и D , где (1) C правильно содержится в D , (2) D имеет полный язык под C- сокращениями, (3) список всех C- сокращений может быть рекурсивно перечислены, и (4) функция F вычислима в C . Возможно, единственным тревожным требованием является последнее требование, но если вы посмотрите на определение f в ссылке, его будет очень легко вычислить для большинства разумных классов C, о которых я могу подумать.СDСDDССеСеС

Райан Уильямс
источник
8

Я думаю , что ответ положителен для и равномерной версии N C . Доказательство Лэднера не использует ничего, кроме того, что вы заявили, и тот факт, что меньший класс представлен рекурсивно и должен работать с небольшими изменениями, но я не проверял детали, взгляните на рецензию Ланса здесь .Сзнак равноLNС


Обновить

Проверьте работу Ладнера о структуре полиномиальной временной сводимости

Вот реферат: два понятия полиномиальной сводимости по времени, обозначенные здесь и P m , были определены Кук и Карп, соответственно. Исследуется абстрактное свойство этих двух соотношений в области вычислимых множеств. Оба отношения оказываются плотными и имеют минимальные пары. Кроме того, существует строго восходящая последовательность с минимальной парой верхних границ последовательности. Наш метод показа плотности дает результат, что если P N P, то есть члены N P - P , которые не являются полиномиальными полными.TпмппNпNп-п

Теорема 1. Если B вычислима , а не в , то существует вычислимая А таким образом, что P , Р м Б , а Б Р Т .пAAпAмпВВTпA

Также см. Раздел 6, в котором обсуждаются обобщения:

Теорема 5. Если является класс времени , то C м и C Т являются возвратными и переходными отношениями и теоремы 1-4 удержания с P заменены C .СмСTСпС

Теорема 7. Если является пространство класса , то C м и C Т являются возвратными и переходными отношениями и теоремы 1-4 удержания с P заменены C .СмСTСпС

Термины класс времени и пространства класса определены в статье.

Кава
источник
Как я понял доказательства Ладнера и Импальяццо, они, похоже, использовали некоторые ингредиенты, специфичные для NP, SAT и многократного сокращения за полиномиальное время. Мой вопрос касается именно того, могут ли эти ингредиенты использоваться более широко.
Андрас Саламон
@ András Salamon: Нет, на самом деле оригинальное доказательство Ладнера не использует какой-либо факт о SAT, кроме того, что он вычислим (см. Теорему 1 выше). В разделе 6 он обсуждает свойства, необходимые для приведения в действие его теорем. Я думаю, что это космический класс. L
Каве
Сзнак равноNССзнак равноAС0
5

Я задал подобный вопрос Питеру Шору в Mathoverflow здесь . По его словам, он не знает о таком результате.

Nпп

AΣяпВΣя-1пВ

Другая интересная проблема заключается в рассмотрении обобщения Ладнера для многообещающих версий семантических классов, таких как обещание БПП, обещаниеMA и т. Д.

Маркос Вильягра
источник
Я забыл упомянуть, что это, конечно, только в отношении PH, и кажется, что это более правдоподобный подход, чем использование какого-либо класса сложности.
Маркос Вильягра
5
Ссылка: mathoverflow.net/questions/9221/…
Райан Уильямс
3
СВппMANС
да, перечисление машин из семантических классов не является рекурсивным. Но обещанные версии семантических классов (обещание BPP, обещаниеMA, ...) действительно синтаксические.
Маркос Вильягра