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

Предполагается, что поскольку обратное подразумевает \ 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} кажется открытым.$\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}$$\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} \subset \mathsf{NPC} \cup \mathsf{P}/\text{poly}$

Предполагая, что $\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}$ (или даже что полиномиальная иерархия не разрушается ни на каком уровне), это $\mathsf{NPI} \subset \mathsf{P}/\text{poly}$ известно, правда или ложь? Какие доказательства могут быть предъявлены за и против?

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

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

Мы применим основную теорему из этой статьи для языков и являющихся языками, а и - классов сложности следующим образом:A 2 C 1 C$A_1$$A_2$$\mathsf{C}_1$$\mathsf{C}_2$

• $A_1 = \varnothing$ (или любой язык в )$\mathsf{P}$
• $A_2 = \text{SAT}$
• $\mathsf{C}_1 = \mathsf{NPC}$
• $\mathsf{C}_2 = \mathsf{NP} \cap \mathsf{P/poly}$

Для ясности мы докажем тот факт, что подразумевает .Н Р Я ⊈ Р / р ö л $\mathsf{NP} \not\subseteq \mathsf{P/poly}$$\mathsf{NPI} \not\subseteq \mathsf{P/poly}$

В предположении, что у нас есть и . Ясно, что и замкнуты при конечных вариациях. Статья Шенинга включает доказательство того, что является рекурсивно презентабельным (точное определение которого можно найти в статье), и самая сложная часть аргумента состоит в том, чтобы доказать, что рекурсивно презентабельно.1 ∉ С 1 2 ∉ С 2 С 1 С 2 С 1 С$\mathsf{NP} \not\subseteq \mathsf{P/poly}$$A_1\not\in\mathsf{C}_1$$A_2\not\in\mathsf{C}_2$$\mathsf{C}_1$$\mathsf{C}_2$$\mathsf{C}_1$$\mathsf{C}_2$

При этих предположениях из теоремы следует, что существует язык , которого нет ни в ни в ; и учитывая, что , он считает, что сводится по к , и, следовательно, . Учитывая, что находится в но не является ни -полным, ни , из этого следует, что .C 1 C 2 A 1 ∈ P A A 2 A $A$$\mathsf{C}_1$$\mathsf{C}_2$$A_1\in\mathsf{P}$$A$$A_2$Н Р Н Р Н Р ∩ Р / р о л у Н Р Я ⊈ Р / р о л $A\in\mathsf{NP}$$A$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP} \cap \mathsf{P/poly}$$\mathsf{NPI} \not\subseteq \mathsf{P/poly}$

Осталось доказать, что рекурсивно презентабельно. В основном это означает, что существует явное описание последовательности детерминированных машин Тьюринга которые все останавливаются на всех входах и таковы, что . Если в моем аргументе есть ошибка, это, вероятно, здесь, и если вам действительно нужно использовать этот результат, вы захотите сделать это осторожно. Во всяком случае, путем согласования всех недетерминированных машин Тьюринга за полиномиальное время (которые могут быть смоделированы детерминистически, потому что мы не заботимся о времени работы каждогоM 1 , M 2 , $\mathsf{NP} \cap \mathsf{P/poly}$$M_1, M_2, \ldots$M k M k M $\mathsf{NP} \cap \mathsf{P/poly} = \{L(M_k):k=1,2,\ldots\}$$M_k$и все полиномы, представляющие верхние границы размера семейства булевых цепей для данного языка, я считаю, что нетрудно получить перечисление, которое работает. По сути, каждый может проверять, соответствует ли его соответствующий NTM за полиномиальное время некоторому семейству схем полиномиального размера вплоть до длины входной строки, которую он задает путем поиска по всем возможным логическим схемам. Если есть соглашение, выводит как NTM, в противном случае он отклоняет (и в результате представляет конечный язык).$M_k$$M_k$

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

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

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

• SAT 'находится в NP (см. Ниже!)
• SAT 'не находится в P / poly: учитывая схемы размера для SAT', мы получаем схемы размера для SAT, но это меньше, чем для некоторых .n g ( n ) k n f ( n )$n^k$$n^{g(n)k}$$n^{f(n)}$$n$
• Нет никакого сокращения P / poly с SAT до SAT ': предположим для противоречия, что существуют схемы размера для SAT, позволяющие использовать шлюзы SAT'. Pick достаточно велико , что , и пусть . Каждый вход SAT в имеет не более входов. Удаляя входные данные заполнения, мы можем обрезать ворота SAT 'в в ворота SAT с менее чем входами, которые мы можем смоделировать, используя - итоговые ворота SAT имеют самое большее входов. Повторяя это и обрабатывая вручную, SAT будет иметь схемы размером примерноn k N g ( $C_n$$n^k$$N$n>NCnnkCn$g(\sqrt{N}) > 2k$$n>N$$C_n$$n^k$$C_n$ C$\sqrt{n}$ nk/2CN$C_{\sqrt{n}}$$n^{k/2}$$C_N$n f ( n )$O(n^k n^{k/2} n^{k/4} \dots) \approx O(n^{2k})$ что меньше для некоторого .$n^{f(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)$$n^{f(n)}$$n$$g(n)$$f(m)$$m=1,2,\dots$$n$$m=n$$g(n)$g ( n ) n n f ( n )$\liminf g(n)/f(n)=0$$g(n)$$n$$n^{f(n)}$$n$,

Мне также было бы интересно увидеть доказательство, взорвав дыры в SAT, как в http://blog.computationalcomplexity.org/media/ladner.pdf . Без требования NP это довольно просто: существует последовательность такая, что никакой размер схемы обнаруживает строки SAT длины ; ограничить SAT строками длины для некоторых .( n k ) k n n 2 2 i$n_1<n_2<\dots$$(n_k)^k$$n$$n_{2^{2^i}}$$i$

(NPI P / poly) (P NP)$\nsubseteq$$\implies$$\neq$