Si un unario el lenguaje existe en NPC entonces P=NP

Question

Tengo una pregunta con respecto a un teorema de la Teoría de la Complejidad.

Se dice que, si existe un único idioma en el NPC entonces P=NP e.g si {1}* en NPC, a continuación, el de arriba es correcta.

Esto significa que existe una Karp reducción de SAT a L, la reducción es el siguiente:

Sea f:φ -> {1}* la función de asignación de un booleano forumlas a unario cadenas.

Dejar Un:{1}* -> {T,F,indefinido}

Definimos el SAT como el siguiente algoritmo:

SAT(φ,A)
     if (|φ| == 1) return φ // trivial case - True or False
     if (A(f(φ)) != undefined) return A(f(φ))
     A(f(φ)) = SAT(φ(T, x2...xn)) || SAT(φ(F, x2...xn))
     return A(f(φ))

Para probar que P=NP, de acuerdo a la hipótesis de que existe un único lenguaje L en NPC Tengo que probar el algoritmo anterior se SENTÓ ejecuta en el polinomio tiempo, he estado intentando por dos días para entender cómo, pero estoy carecen del conocimiento, ¿alguien puede ayudar?

La intuición es que una cadena de longitud n tiene 1 representación en unario idioma mientras que en binario idiomas {0,1}* dispone de 2^n de las representaciones.

Gracias, Max.

Answer 1

Deje $L$ ser un NP-completo unario idioma. Desde $L$ es NP-completo, hay un polytime reducción de la $f$ de SAT a $L$. Desde $f$ es polytime, $|f(x)| \leq C|x|^d$ algunos $C,d$. Ahora vamos a describir un polytime algoritmo para el SAT.

Denotar la entrada por $\phi$, una fórmula en la $n$ variables $x_1,\ldots,x_n$; suponemos que la $|\phi| \geq n$. El algoritmo procede en $n$ etapas, la creación de una secuencia de listas de $L_n,\ldots,L_0$. La lista de $L_k$ se compone de una lista de pares $\{(f(\psi_i),\psi_i)\}$ donde $\psi_i$ es una fórmula que resulta de la sustitución de los valores de $x_{k+1},\ldots,x_n$ $\phi$ y la simplificación. Mantenemos la invariante que $\phi$ es válido si y sólo si uno de los $\psi_i$ es válido.

La lista inicial $L_n$ se compone de los par $(f(\phi),\phi)$. Dada la lista de $L_k$, podemos construir la lista $L_{k-1}$ en dos pasos:

1. Para cada una de las $(f(\psi),\psi) \in L_k)$, agregar a $L_{k-1}$ los dos pares de $(f(\psi|_{x_k=\top}),\psi|_{x_k=\top})$$(f(\psi|_{x_k=\bot}),\psi|_{x_k=\bot})$; después de la sustitución de un valor de $x_k$, podemos simplificar la fórmula resultante.
2. Para cada una de las $m$, de todos los pares de la forma $(1^m,\psi)$ (si cualquier) conservar sólo una.

No es difícil comprobar que el invariante es, de hecho, se mantiene. El conjunto final $L_0$ podría contener potencialmente $(f(\top),\top)$$(f(\bot),\bot)$; la fórmula es válido si y sólo si contiene la antigua.

Cada lista de $L_k$ tiene de tamaño en la mayoría de las $C|\phi|^d$, y por lo que el algoritmo se ejecuta en el polinomio de tiempo.

Answer 2

La página de la wiki en unario idiomas tiene también ese teorema, y un puntero al papel de Piotr Berman.

Piotr Berman. Relación entre la densidad y determinista de la complejidad de NP-completo idiomas. En Actas de la 5ª Conferencia sobre Autómatas, Lenguajes de Programación y, págs. 63–71. Springer-Verlag. Lecture Notes in Computer Science #62. 1978.

Y una nota: usted no tiene que usar siempre se SENTÓ a cuando se trabaja con NP-completo los problemas. Aunque siempre es posible hacerlo, otros problemas pueden ser mucho más fáciles de reducir para el problema en cuestión.