¿Cuáles son las complejidades de los siguientes subconjuntos SAT?

Suponga que $P \neq NP$

Deje usar la siguiente notación para la tetración (es decir. ${}^ia$ ). ${}^ia = \underbrace{a^{a^{\cdot^{\cdot^{\cdot^{a}}}}}}_{i \mbox{ times}}$

| x | es el tamaño de la instancia x.

Deje L ser una lengua, $L|_{f(i)\leq |x| < g(i)} := \{ x \in L \mbox{ | } \exists i \in \mathbb{N}\mbox{, } f(i) \leq |x| < g(i) \}$

¿Cuál es la complejidad de los siguientes idiomas:

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

Como , no pueden ser tanto en P bajo la suposición de que . Como ambos tienen agujeros exponenciales, no creo que SAT pueda reducirse a uno. $L_1 \sqcup L_2 = SAT$ $P \neq NP$

Por lo tanto, la intuición sería que ambos están en NPI, pero no puedo encontrar una prueba o una prueba.

Otros dos idiomas son $L_3 = SAT|_{|x|={}^{2i+1}2}$ $L_4 = SAT|_{|x|={}^{2i}2}$

Si uno de los dos está en NPC, el otro está en P porque para cada instancia de uno, no se puede transformar en una instancia mayor del otro porque es de tamaño exponencial, y las instancias más pequeñas tienen un tamaño logarítmico. Aún por intuición, no hay razón para que tengan una complejidad diferente. ¿Cuál sería su complejidad?

La prueba de Ladner de los problemas de NPI bajo la suposición usa lenguajes como o , pero y no se construyen por diagonalización. $P \neq NP$ $L_1$ $L_2$ $L_1$ $L_2$

cc.complexity-theory np-hardness complexity-classes Ludovic Patey
fuente

Sus idiomas tienen muchas instancias que se completan con la adición de cláusulas adicionales que no interactúan entre sí. Por lo tanto, parecen NPI por el argumento de diagonalización de Schöning? dx.doi.org/10.1016/0304-3975(82)90114-1

András Salamon

Después de "no pueden estar ambos en P", debería decir "bajo el supuesto de que P

NP ..."

\neq

$\ne$

Emil

Agregué "bajo el supuesto" incluso si ya establecí este supuesto antes.

Ludovic Patey

Si L1 o L2 tienen NP completo, entonces la conjetura del isomorfismo falla, ya que ni L1 ni L2 son cilindros (tiene una función de relleno). Por lo tanto, demostrar que uno de ellos es NP-completo requiere técnicas no relativizantes. Sin embargo, todavía no veo ninguna barrera para demostrar que uno de ellos no es NP completo.

Joshua Grochow

Puede que haya sido un poco confuso con mis cuantificadores. Permítaseme añadir paréntesis: no existe una máquina de Oracle en tiempo poli

tal que [para todas las

[

resuelve

]]. Es decir, para cualquier

, puede ser que para algunos X,

resuelve uno de los idiomas, pero no puede ser verdad para todos

. Entonces, por ejemplo,

sin el oráculo podría resolver

(no relativizado), pero no importa qué

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$ es decir, habrá algún oráculo tal que no resuelva ninguno de los dos idiomas.

Joshua Grochow

Respuestas:

Creo que ambos son NPI bajo la suposición más fuerte (pero obviamente cierto) de que NP no está en "infinitamente frecuente P", es decir, cada algoritmo de tiempo polinomial A y cada n suficientemente grande, A no resuelve SAT en entradas de longitud n.

En este caso, dichos lenguajes no están en P, pero tampoco pueden ser NP completos, ya que de lo contrario una reducción de SAT a un lenguaje L con agujeros grandes dará un algoritmo para SAT que tenga éxito en estos agujeros.

Tal suposición también es necesaria, ya que de lo contrario los idiomas pueden estar en P o NP-completo, dependiendo de dónde se encuentren las "longitudes de entrada fáciles".

Boaz Barak
fuente

@Boaz: Entiendo lo que quieres decir con "tal suposición es necesaria", pero tengo problemas para formalizar la necesidad. Creo que uno construye un oráculo

, sin demasiada dificultad, de modo que

, hay una máquina de tiempo polivinílico

tal que

decide

en infinitas longitudes de entrada, sin embargo,

son

-intermedio.

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$

Joshua Grochow

Lo que quise decir es que la suposición

no es suficiente por sí sola para mostrar que estos lenguajes son NP intermedios, ya que no podemos descartar el caso de que

pero hay un algoritmo que resuelve SAT exactamente en las entradas que

no es trivial, en cuyo caso

estaría en

sería 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 Barak

@Boaz: Ah, por supuesto. Una formalización de esto es un oráculo

tal que

pero

(que creo, similar al otro oráculo que mencioné, no es demasiado difícil de construir). (PD: al usar @name, se asegura que el otro usuario sea notificado de tu comentario).

X

$X$

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

$P^X \neq NP^X$

L_{1}^{X} \in P

$L_1^X \in P$

Joshua Grochow

@Joshua: Si

sea

una máquina Poly-time para

, entonces

también resolvería

ya que el caso sin consultar al oráculo es solo un caso especial. Entonces, si puede crear una

como la describe, demuestra que

por lo tanto, realmente no entiendo cómo podría hacerlo.

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$

Arthur MILCHIOR

@Joshua: sobre su primer comentario bajo Boaz Barak, si

resolver

(en un número infinito de longitudes de entrada) entonces supongo que usted quiere que su

al menos que sea un oráculo para

. Pero ya que puede tener consulta a

en la fórmula #, a continuación, de hecho, que incluso necesitar

ser un oráculo para

. ¿Cómo puedes demostrar que una definición tan recursiva es correcta? No me parece nada claro. (# Supongo que SAT ^ X es SAT donde X también puede estar en las cláusulas)

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$

Arthur MILCHIOR