Quais são as complexidades dos seguintes subconjuntos SAT?

Assuma $P \neq NP$

Vamos usar a seguinte notação para tetração (ie. ${}^ia$ ). ${}^ia = \underbrace{a^{a^{\cdot^{\cdot^{\cdot^{a}}}}}}_{i \mbox{ times}}$

| x | é o tamanho da instância x.

Seja L uma língua, $L|_{f(i)\leq |x| < g(i)} := \{ x \in L \mbox{ | } \exists i \in \mathbb{N}\mbox{, } f(i) \leq |x| < g(i) \}$

Qual é a complexidade dos seguintes idiomas:

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

Como , eles não podem ser ambos em P sob a suposição de que . Como ambos têm buracos exponenciais, acho que o SAT não pode ser reduzido a um. $L_1 \sqcup L_2 = SAT$ $P \neq NP$

Portanto, a intuição seria que ambos estão no NPI, mas não consigo encontrar uma prova ou desaprovação.

Duas outras línguas são $L_3 = SAT|_{|x|={}^{2i+1}2}$ $L_4 = SAT|_{|x|={}^{2i}2}$

Se um dos dois estiver no NPC, o outro no P, porque para cada instância de um, ele não pode ser transformado em uma instância maior do outro porque é de tamanho exponencial e as instâncias menores têm um tamanho logarítmico. Ainda por intuição, não há razão para que eles tenham uma complexidade diferente. Qual seria a complexidade deles?

A prova de Ladner dos problemas de NPI sob a premissa de usa linguagens como ou , mas e não são construídos por diagonalização. $P \neq NP$ $L_1$ $L_2$ $L_1$ $L_2$

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

Seus idiomas têm muitas instâncias preenchidas pela adição de cláusulas extras que não interagem entre si. Eles, portanto, parecem NPI pelo argumento da diagonalização de Schöning? dx.doi.org/10.1016/0304-3975(82)90114-1

András Salamon

Depois de "eles não podem estar ambos em P", deve-se dizer "sob a suposição de que P

NP ..."

\neq

$\ne$

Emil

Eu adicionei "sob a suposição", mesmo que eu já tenha definido essa suposição antes.

Ludovic Patey

Se L1 ou L2 for NP-completo, a Conjectura de Isomorfismo falhará, pois nem L1 nem L2 são um cilindro (tem uma função de preenchimento). Portanto, provar que um deles é NP-completo requer técnicas de não relativização. Ainda não vejo nenhuma barreira para mostrar que um deles não é NP-completo.

Joshua Grochow 22/09/10

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$ ou seja, haverá algum oráculo que não resolve nenhum dos idiomas.

Joshua Grochow

Eu acho que ambos são NPI sob a suposição mais forte (mas obviamente verdadeira) de que NP não está "infinitamente frequentemente P" - ou seja, todo algoritmo de tempo polinomial A e todo n suficientemente grande, A falham em resolver SAT em entradas de comprimento n.

Nesse caso, essas linguagens não estão em P, mas também não podem ser NP completas, pois, caso contrário, uma redução de SAT para uma linguagem L com orifícios grandes fornecerá um algoritmo para SAT com êxito nesses orifícios.

Essa suposição também é necessária, pois, caso contrário, os idiomas podem estar em P ou NP-completo, dependendo de onde os "comprimentos fáceis de entrada" estiverem localizados.

Boaz Barak
fonte

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$

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$

X

$X$

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

$P^X \neq NP^X$

L_{1}^{X} \in P

$L_1^X \in P$

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$

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$

Quais são as complexidades dos seguintes subconjuntos SAT?

Respostas: