Каковы сложности следующих подмножеств SAT?

Предположим, $P \neq NP$

Давайте использовать следующие обозначения для тетратации (то есть. ). ${}^ia$ ${}^ia = \underbrace{a^{a^{\cdot^{\cdot^{\cdot^{a}}}}}}_{i \mbox{ times}}$

| Х | это размер экземпляра х.

Пусть L язык, $L|_{f(i)\leq |x| < g(i)} := \{ x \in L \mbox{ | } \exists i \in \mathbb{N}\mbox{, } f(i) \leq |x| < g(i) \}$

В чем сложность следующих языков:

$L_1 = SAT|_{{}^{2i}2 \leq |x| < {}^{2i+1}2}$ $L_2 = SAT|_{{}^{2i+1}2 \leq |x| < {}^{2i+2}2}$

Поскольку , они не могут быть оба в P при условии, что . Так как там есть экспоненциальные дыры, я не думаю, что SAT можно сократить до одного. $L_1 \sqcup L_2 = SAT$ $P \neq NP$

Следовательно, интуиция могла бы заключаться в том, что они оба в NPI, но я не могу найти доказательства или опровержения.

Два других языка: $L_3 = SAT|_{|x|={}^{2i+1}2}$ $L_4 = SAT|_{|x|={}^{2i}2}$

Если один из обоих находится в NPC, другой находится в P, потому что для каждого экземпляра одного он не может быть преобразован в больший экземпляр другого, потому что он имеет экспоненциальный размер, а экземпляры меньшего размера имеют логарифмический размер. Тем не менее, благодаря интуиции, нет никаких причин, почему они будут иметь другую сложность. Какова будет их сложность?

Доказательство Лэднером проблем NPI в предположении использует такие языки, как или , но и не построены диагонализацией. $P \neq NP$ $L_1$ $L_2$ $L_1$ $L_2$

cc.complexity-theory np-hardness complexity-classes Людовик Патей
источник

У ваших языков есть много примеров, которые дополняются добавлением дополнительных предложений, которые не взаимодействуют друг с другом. Поэтому они кажутся NPI аргументом диагонализации Шенинга? dx.doi.org/10.1016/0304-3975(82)90114-1

Саламон

После того, как «они не могут быть оба в P», следует сказать «при условии, что P NP ...»

\neq

$\ne$

Эмиль

Я добавил «в предположении», даже если я уже установил это предположение раньше.

Людовик Пати

Если L1 или L2 NP-полны, то гипотеза об изоморфизме не выполняется, поскольку ни L1, ни L2 не являются цилиндрами (не имеют функции заполнения). Поэтому доказательство того, что один из них является NP-полным, требует нерелятивизирующих методов. Я пока не вижу никаких препятствий для того, чтобы показать, что один из них не является NP-завершенным.

Джошуа Грохов

Возможно, я был немного неясен с моими квантификаторами. Позвольте мне добавить круглые скобки: не существует многоракурсной машины оракула , которая [для всех [ решает ]]. То есть, для любого , может быть , что для некоторого X, решает одну из языков, но это не может быть правдой для всех . Так, например, без оракула может решить (нерелятивизированный), но независимо от того, что такое , будет такой оракул, который не решит ни один из языков.

M

$M$

X

$X$

M^{X}

$M^X$

L_{1}^{X} o r L_{2}^{X}

$L_1^X or L_2^X$

M

$M$

M^{X}

$M^X$

X

$X$

M

$M$

L_{1}

$L_1$

M

$M$

Джошуа Грохоу

Ответы:

Я думаю, что оба являются NPI при более строгом предположении (но, очевидно, верно), что NP не находится в «бесконечно часто P» - то есть, каждый алгоритм A за полиномиальное время и каждый достаточно большой n, A не в состоянии решить SAT на входах длины n.

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

Такое предположение также необходимо, так как в противном случае языки могут быть в P или NP-завершены, в зависимости от того, где расположены «простые длины ввода».

Боаз Барак
источник

@ Боаз: Я вроде понимаю, что вы подразумеваете под «такое предположение необходимо», но у меня возникают проблемы с формализацией необходимости. Я думаю, что можно построить оракула без особых трудностей, чтобы , есть машина многовидового такая, что решает на бесконечном множестве входных длин, но и являются -средними.

X

$X$

P^{X} \neq N P^{X}

$P^X \neq NP^X$

M

$M$

M^{X}

$M^X$

S A T^{X}

$SAT^X$

L_{1}^{X}

$L_1^X$

L_{2}^{X}

$L_2^X$

N P^{X}

$NP^X$

Джошуа Грохов

Я имел в виду, что предположения недостаточно для того, чтобы показать, что эти языки являются NP-промежуточными, поскольку мы не можем исключить случай, когда но существует алгоритм, который решает SAT именно на входах. что нетривиален, в этом случае будет в а будет NPC.

N P \neq P

$NP\neq P$

N P \neq P

$NP\neq P$

L_{1}

$L_1$

L_{1}

$L_1$

P

$P$

L_{2}

$L_2$

Вооз Барак

@Boaz: ну конечно. Одна формализация этого оракула такова, что но (который, как я полагаю, похож на другого оракула, о котором я упоминал, не так уж сложно построить). (PS - Используя @name, он гарантирует, что другой пользователь будет уведомлен о вашем комментарии.)

X

$X$

P^{X} \neq N P^{X}

$P^X \neq NP^X$

L_{1}^{X} \in P

$L_1^X \in P$

Джошуа Грохов

@ Джошуа: Если пусть будет машиной Poly-time для , тогда также решит поскольку случай без запроса к оракулу - это только особый случай. Поэтому, если вы можете создать как вы его описали, вы докажете, что следовательно, я действительно не понимаю, как вы могли это сделать.

L_{1}^{X} \in P

$L_1^X\in P$

M

$M$

L_{1}^{X}

$L_1^X$

M

$M$

L_{1}

$L_1$

X

$X$

P_{1} \in P

$P_1\in P$

Артур МИЛЬЧИОР

@Joshua: о вашем первом комментарии под Боазом Бараком, если решит (на бесконечно многих входных длинах), то, я думаю, вы хотите, чтобы ваш был оракулом для . Но так как вы можете иметь запрос к в формуле #, то на самом деле вы даже не нужно , чтобы быть оракулом для . Как вы можете показать, что такое рекурсивное определение верно? Это не кажется мне совершенно ясным. (# Я думаю, что SAT ^ X - это SAT, где X также может быть в предложениях)

M \in P^{X}

$M\in P^X$

S A T^{X}

$SAT^X$

X

$X$

S A T

$SAT$

X

$X$

X

$X$

S A T^{X}

$SAT^X$

Артур МИЛКИОР