Intersección de idiomas en NP

Solo un comentario extendido para explicar mejor el comentario de ARi (lo estaba escribiendo mientras lo veía).

Es suficiente utilizar un enfoque de "gran brecha" similar al utilizado en el teorema de Lardner; por ejemplo:

$A_1 = \{ x \mid x \in SAT \land f(|x|) \text { is even}\} \cup \{x \mid f(|x|) \text{ is odd} \}$

$A_2 = \{ x \mid x \in SAT \land f(|x|) \text { is odd}\} \cup \{x \mid f(|x|) \text{ is even} \}$

Donde es una función creciente lo suficientemente lenta computable en tiempo polinómico. Véase, por ejemplo, su construcción en la prueba del teorema de Ladner en el Apéndice A.1 de Lenguas uniformemente duras . $f$

Por construcción no son NPC, sino $A_1, A_2$ $A_1 \cap A_2 = SAT$

Marzio De Biasi
fuente

¿Por qué

no son NPC?

A_{1}

$A_1$

A_{2}

$A_2$

Mateus de Oliveira Oliveira

@MateusdeOliveiraOliveira: por diagonalización retrasada

no es NPC (

es un problema NP-intermedio artificial); ver la prueba vinculada para más detalles. Por supuesto, debemos suponer que

; el caso

ya ha sido descartado por Gamow en el comentario anterior.

{x ∣ x \in S A T \land f (| x |) is even}

$\{ x \mid x \in SAT \land f(|x|) \text{ is even}\}$

A_{1}

$A_1$

P \neq N P

$P \neq NP$

P = N P

$P = NP$

Marzio De Biasi

¿No se puede considerar cualquier función polytime?

ARi

@ARi: no, debe ser lo suficientemente lento como para crear espacios grandes para evitar la completitud de NP (para permitir la diagonalización retrasada). Intentaré escribir una prueba formal en los próximos días.

Marzio De Biasi

f

$f$

Intersección de idiomas en NP

Respuestas: