Содержится ли NPI в P / poly?

29

Предполагается, что поскольку обратное подразумевает \ mathsf {PH} = \ Sigma_2 . Теорема Ладнера устанавливает, что если \ mathsf {P} \ ne \ mathsf {NP}, то \ mathsf {NPI}: = \ mathsf {NP} \ setminus (\ mathsf {NPC} \ cup \ mathsf {P}) \ ne \ emptyset , Однако доказательство, по-видимому, не обобщается на \ mathsf {P} / \ text {poly}, поэтому существует вероятность \ mathsf {NPI} \ subset \ mathsf {P} / \ text {poly} т.е. \ mathsf {NP} \ подмножество \ mathsf {NPC} \ cup \ mathsf {P} / \ text {poly} кажется открытым.NPP/polyPH=Σ2PNPNPI:=NP(NPCP)P/polyNPIP/polyNPNPCP/poly

Предполагая, что NPP/poly (или даже что полиномиальная иерархия не разрушается ни на каком уровне), это NPIP/poly известно, правда или ложь? Какие доказательства могут быть предъявлены за и против?

Ванесса
источник
5
Итак, «что произойдет, если все проблемы в NP либо NP-полны, либо в P \ poly»? с одной стороны, это будет означать небольшие схемы для факторинга
Сашо Николов
1
ps: пост будет более читабельным, если вы произнесете "это" в цитируемой части. Также вы можете использовать NPP/poly вместо NPP качестве предположения.
Каве
4
Разве аргумент-заполнитель не покажет, что это не может произойти, если NP P / poly?
Питер Шор
3
@PeterShor: Я, наверное, плотный, но как именно это будет работать?
Ванесса
8
@ Скварк: ты не дремучий ... Я точно не определился, как это будет работать, и, думаю, немного ошибочно сформулировал результат. Но вот моя основная идея. Предположим, что NP-полные проблемы не могут быть решены за субэкспоненциальное время и рекомендации. Возьмите NP-полную задачу X и добавьте ее так, чтобы самый быстрый алгоритм для нее был едва ли субэкспоненциальным. Тогда это NPI, так что это может быть решено в P / Poly. Это означает, что NP-полная проблема X может быть решена во времени только немного медленнее, чем время P / poly. Путем полиномиальной редукции теперь все NP-полные задачи могут быть решены немного медленнее, чем время P / poly.
Питер Шор

Ответы:

18

Вот возможная альтернатива дополнительному аргументу, основанному на обобщении теоремы Леднера Шёнингом. Чтобы понять аргумент, вам нужен доступ к этому документу (который, к сожалению, для многих будет за стеной оплаты):

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

Мы применим основную теорему из этой статьи для языков и являющихся языками, а и - классов сложности следующим образом:A 2 C 1 C 2A1A2C1C2

  • PA1= (или любой язык в )P
  • A2=SAT
  • C1=NPC
  • C2=NPP/poly

Для ясности мы докажем тот факт, что подразумевает .Н Р ЯР / р ö л уNPP/polyNPIP/poly

В предположении, что у нас есть и . Ясно, что и замкнуты при конечных вариациях. Статья Шенинга включает доказательство того, что является рекурсивно презентабельным (точное определение которого можно найти в статье), и самая сложная часть аргумента состоит в том, чтобы доказать, что рекурсивно презентабельно.1С 1 2С 2 С 1 С 2 С 1 С 2NPP/polyA1C1A2C2C1C2C1C2

При этих предположениях из теоремы следует, что существует язык , которого нет ни в ни в ; и учитывая, что , он считает, что сводится по к , и, следовательно, . Учитывая, что находится в но не является ни -полным, ни , из этого следует, что .C 1 C 2 A 1P A A 2 A AC1C2A1PAA2Н Р Н Р Н РР / р о л у Н Р ЯР / р о л уANPANPNPNPP/polyNPIP/poly

Осталось доказать, что рекурсивно презентабельно. В основном это означает, что существует явное описание последовательности детерминированных машин Тьюринга которые все останавливаются на всех входах и таковы, что . Если в моем аргументе есть ошибка, это, вероятно, здесь, и если вам действительно нужно использовать этот результат, вы захотите сделать это осторожно. Во всяком случае, путем согласования всех недетерминированных машин Тьюринга за полиномиальное время (которые могут быть смоделированы детерминистически, потому что мы не заботимся о времени работы каждогоM 1 , M 2 , NPP/polyM1,M2,M k M k M kNPP/poly={L(Mk):k=1,2,}Mkи все полиномы, представляющие верхние границы размера семейства булевых цепей для данного языка, я считаю, что нетрудно получить перечисление, которое работает. По сути, каждый может проверять, соответствует ли его соответствующий NTM за полиномиальное время некоторому семейству схем полиномиального размера вплоть до длины входной строки, которую он задает путем поиска по всем возможным логическим схемам. Если есть соглашение, выводит как NTM, в противном случае он отклоняет (и в результате представляет конечный язык).MkMk

Основная интуиция, лежащая в основе аргумента (который скрыт внутри результата Шенинга), состоит в том, что у вас никогда не может быть двух «хороших» классов сложности (то есть классов с рекурсивными представлениями), которые не пересекаются друг с другом. «Топология» сложных классов не позволит этого: вы всегда можете правильно построить язык между двумя классами, каким-то образом чередуя их для очень длинных отрезков входных длин. Теорема Ладнера показывает это для и , а обобщение Шенинга позволяет вам сделать то же самое для многих других классов.N P CPNPC

Джон Уотроус
источник
7
Это ссылка на бесплатные публикации Шенинга
Алессандро
1
Большое спасибо за ответ! Самое смешное, что я знал теорему Шоенинга, но по какой-то глупой причине подумал, что она не применима в этом случае. Кстати, текст находится в свободном доступе даже в научной науке
Ванесса
1
@Squark: Не глупо подозревать, что теорема Шенинга неприменима, учитывая, что P / poly включает нерекурсивные языки. Я полагаю, это удача, что мы можем пересечь его с NP и все же получить результат.
Джон Уотроус
1
@JohnWatrous: Да, именно поэтому я запутался
Ванесса
15

Я просто хотел бы записать некоторую версию аргумента заполнения, как описано в комментариях. Я не понимаю, зачем нужен разрыв. Мы хотим показать, что если NP не содержится в P / poly, то существует NP-промежуточная проблема, не содержащаяся в P / poly.

Существует неограниченная функция такая, что SAT не имеет цепей с размером меньше , и поэтому существует функция которая не ограничена, увеличивается и . Обозначим через SAT 'язык, полученный путем заполнения строк SAT длиной до . Затем:n f ( n ) g g ( n ) = o ( f ( n ) ) n n g ( n )fnf(n)gg(n)=o(f(n))nng(n)

  • SAT 'находится в NP (см. Ниже!)
  • SAT 'не находится в P / poly: учитывая схемы размера для SAT', мы получаем схемы размера для SAT, но это меньше, чем для некоторых .n g ( n ) k n f ( n ) nnkng(n)knf(n)n
  • Нет никакого сокращения P / poly с SAT до SAT ': предположим для противоречия, что существуют схемы размера для SAT, позволяющие использовать шлюзы SAT'. Pick достаточно велико , что , и пусть . Каждый вход SAT в имеет не более входов. Удаляя входные данные заполнения, мы можем обрезать ворота SAT 'в в ворота SAT с менее чем входами, которые мы можем смоделировать, используя - итоговые ворота SAT имеют самое большее входов. Повторяя это и обрабатывая вручную, SAT будет иметь схемы размером примерноn k N g ( CnnkNn>NCnnkCng(N)>2kn>NCnnkCn Cn nk/2CNOCnnk/2CNn f ( n ) nO(nknk/2nk/4)O(n2k) что меньше для некоторого .nf(n)n

Редактировать:

Выбор немного сложен. Если вы счастливы поставить SAT 'в обещанную версию NP, этот бит не нужен.g

Определите как максимальное целое число, чтобы в SAT не было цепочки размером для длины строк. Определите с помощью алгоритма, который вычисляет для и останавливается после времени или когда , и возвращает пол квадратного корня из наибольшего значения, найденного за это время , Таким образом, не ограничено и и могут быть вычислены за время . Теперь обратите внимание, что приведенные выше аргументы основаны только на том, что SAT не имеет цепей размером для бесконечного числаn f ( n ) n g ( n ) f ( m ) m = 1 , 2 , n m = n g ( n )f(n)nf(n)ng(n)f(m)m=1,2,nm=ng(n)g ( n ) n n f ( n ) nlim infg(n)/f(n)=0g(n)nnf(n)n,

Мне также было бы интересно увидеть доказательство, взорвав дыры в SAT, как в http://blog.computationalcomplexity.org/media/ladner.pdf . Без требования NP это довольно просто: существует последовательность такая, что никакой размер схемы обнаруживает строки SAT длины ; ограничить SAT строками длины для некоторых .( n k ) k n n 2 2 i in1<n2<(nk)knn22ii

Колин Маккуиллан
источник
1
Увидев ответ @ JohnWatrous, мне напомнили о доказательстве Impagliazzo теоремы Ладнера с помощью отступов (см. Приложение Дауни и Фортноу «Равномерно жесткие языки»: cs.uchicago.edu/~fortnow/papers/uniform.pdf ). Фактически, ваше доказательство - это, по сути, доказательство Ладнера, проведенное Импальяццо, но адаптированное к этой ситуации. Ухоженная!
Джошуа Грохов
1
Большое спасибо за ответ! Я извиняюсь, что не выбрал его, но мне пришлось выбрать один, и аргумент Уотроуса был легче понять, поскольку он использовал результат, который я уже знал. Это довольно субъективный способ выбора, но я не мог сделать лучше. В любом случае, здорово иметь более одного способа получить интересный результат
Ванесса
1
@Squark: абсолютно - и я также предположил, что теорема Шенинга не применима.
Колин МакКиллан
-13

(NPI P / poly) (P NP)

ВЗН
источник
8
он известен и тривиален: если P = NP, то . и это не вопрос, вопрос обратный тому, что вы написали, и Колин убедительно ответил, насколько я понимаю. NPINP=PP/pol
Сашо Николов
вопрос озаглавлен «Содержится ли NPI в P / Poly», и думаю, что это разумный ответ, не уверен, что он действительно тривиален из-за того, как обычно определяется NPI (как зависит от P NP) ... этот ответ не дает конфликт с другим ответом ...
взн
9
На самом деле это даже более очевидно тривиально: если P = NP, NPI пуст. Вопрос четко сформулирован так: «Не содержит ли NP в P / poly значение NPI, а не в P / poly. Поэтому ваш ответ 1) утверждает, что тривиальный факт является открытой проблемой 2) не решает вопрос
Сашо Николов
8
Не может заботиться о баллах. В последний раз: мой первый комментарий, ответ Колина, и вопрос сам по себе связанно с гораздо менее тривиальным и более интересным обратным пустой импликацией вы записали.
Сашо Николов
11
-1: иногда теряющий очко чувствует себя как раз
Алессандро Косентино