¿Existe un lenguaje NP-completo que contiene precisamente la mitad de las instancias de n bits?

¿Existe un lenguaje NP (preferiblemente natural) completo , de modo que por cada retenciones? En otras palabras, contiene precisamente la mitad de todas las instancias de bits. $L\subseteq \{0,1\}^*$ $n\geq 1$

| L \cap {0, 1}^{n} | = 2^{n - 1}

$|L\cap \{0,1\}^n|=2^{n-1}$

L

$L$

n

$n$

cc.complexity-theory np np-complete Andras Farago
fuente

Sería muy sorprendente si no lo hay, pero pensarlo durante unos minutos no pudo encontrar una construcción.

Kaveh

FWIW hay una

que es NP-hard y en NP / POLY ...

L

$L$

Neal Young

Para una codificación binaria byectiva

de fórmulas CNF,

satisfactoria

insatisfactorio

debería funcionar.

e

$e$

{e (φ) 1 | φ

$\{e(\varphi)1\ |\ \varphi$

} \cup {e (φ) 0 | φ

$\} \cup \{e(\varphi)0\ |\ \varphi$

}

$\}$

Klaus Draeger el

@KlausDraeger La insatisfacción no es una propiedad NP, a menos que NP = co-NP.

Andras Farago

¿Hay algún oráculo

tal que no exista

con esta propiedad?

O

$O$

L \in {N P - C o m p l e t e}^{O}

$\mathcal{L}\in {\bf NP-Complete}^O$

Erfan Khaniki el

Respuestas:

Hice esta pregunta hace unos años y Boaz Barak la respondió positivamente .

La declaración es equivalente a la existencia de un lenguaje NP-completo donde es computable en tiempo polinómico. $L$ $|L_n|$

Considere fórmulas booleanas y SAT. Usando relleno y modificando ligeramente la codificación de las fórmulas, podemos asegurarnos de que y tengan la misma longitud. $\varphi$ $\lnot \varphi$

Deje ser una codificación que $\langle\ \rangle$

para todas las fórmulas y para todas las asignaciones de verdad , . $\varphi$ $\tau \in \{0,1\}^{|\varphi|}$ $|\langle\varphi\rangle| = |\langle\varphi, \tau\rangle|$
es computable en tiempo polinómico. $|\langle\varphi\rangle| \mapsto |\varphi|$
El número de fórmulas con longitud codificada es computable en tiempo polinómico. $n$

Considere

L := {⟨ φ ⟩ ∣ φ \in S A T} \cup {⟨ φ, τ ⟩ ∣ τ ⊨ φ and \exists σ < τ σ ⊨ φ}

$L := \{\langle\varphi\rangle \mid \varphi \in \mathsf{SAT} \} \cup \{\langle \varphi, \tau \rangle \mid \tau \vDash \varphi \text{ and } \exists \sigma<\tau\ \sigma\vDash\varphi \}$

Es fácil ver que es NP-completo. $L$

Si , el número de asignaciones de verdad que satisfacen es igual al número de asignaciones de verdad satisfactorias . Agregando mismo, se suma al número de asignaciones de verdad satisfactorias para . $\varphi \in \mathsf{SAT}$

τ ⊨ φ and \exists σ < τ σ ⊨ φ

$\tau \vDash \varphi \text{ and } \exists \sigma<\tau\ \sigma\vDash\varphi$

- 1

$- 1$

φ

$\varphi$

φ

$\varphi$

$2^{|\varphi|}$ $\tau$ $\varphi$ $\lnot \varphi$ $\varphi$ $2(2^{|\varphi|}+1)$ $\langle\varphi\rangle$ $\langle\lnot \varphi\rangle$ $\langle\varphi, \tau\rangle$ $\langle \lnot\varphi, \tau\rangle$ $\tau \in \{0,1\}^{|\varphi|}$ $2^{|\varphi|}$ $2^{|\varphi|+1}+2$ $L$ $n$ $L$ $\varphi$ $n$ $2^{|\varphi|}$

Ryan O'Donnell
fuente

Incluso si esta es la solución deseada, esta es una respuesta claramente solo de enlace.

user2943160

para ser claros, no hay nada especial en SAT, esto funcionaría con cualquier predicado verificador para un problema NP-completo.

Kaveh

ϕ

$\phi$

\neg ϕ

$\lnot \phi$

τ

$\tau$

@Neal, deje que V (x, y) sea un verificador para un problema de NP completo. Considere W (x, b, y): = V (x, y) = b. Todavía está NP-completo y cada y es testigo de x, 0 o x, 1. Sin embargo, no es tan bueno como el SAT.

Kaveh

A = {(ϕ, b, τ) : (τ satisfies ϕ) \leftrightarrow b = 1} ?

$A = \{(\phi, b, \tau) : (\tau \mbox{ satisfies } \phi) \leftrightarrow b=1\}?$

B = {(ϕ, b) : τ \in S A T \leftrightarrow b = 1}

$B = \{(\phi, b) : \tau \in SAT \leftrightarrow b = 1\}$

A \cup B

$A\cup B$

A

$A$

C = {(ϕ, b) : \exists τ . [(τ satisfies ϕ) \leftrightarrow b = 1]}

$C=\{(\phi, b) : \exists \tau.~[(\tau \mbox{ satisfies } \phi) \leftrightarrow b=1]\}$

Aquí hay una sugerencia de por qué podría ser difícil encontrar un ejemplo de eso, aunque estoy de acuerdo con el comentario de Kaveh de que sería sorprendente si no existiera. [No es una respuesta, pero es demasiado larga para un comentario.]

$L$ $L^{=n} := |L \cap \{0,1\}^n| = 2^{n-1}$ $L \cap \{0,1\}^n$ $\{0,1\}^n \backslash L$ $\mathsf{NP}$ $f\colon \{0,1\}^* \to \{0,1\}^*$ $x \in L$ $f(x) \notin L$ $f$ $\mathsf{NP} = \mathsf{coNP}$ $f$ $\mathsf{NP}$ $\mathsf{coNP}$

$\mathsf{EXP}$ $\mathsf{coNP} \subseteq \mathsf{NTIME}(2^{(\log n)^{O(1)}}) =: \mathsf{NQP}$ $\mathsf{PH} \subseteq \mathsf{NQP}$ $\mathsf{PH} \subseteq \mathsf{NQP}$

$L$

Por supuesto, este es también el tipo de cosas en las que alguien vendrá con un ejemplo y veremos fácilmente cómo se resuelve esta objeción, pero solo quería lanzar esto para decir cómo cualquier cosa con una biyección lo suficientemente simple puede No funciona (a menos que las creencias ampliamente aceptadas sean falsas).

$L$

Joshua Grochow
fuente