Si P = NP, ¿por qué

Aparentemente, si ${\sf P}={\sf NP}$ , todos los idiomas en ${\sf P}$ excepto $\emptyset$ y $\Sigma^*$ serían ${\sf NP}$ -completos.

¿Por qué estos dos idiomas en particular? ¿No podemos reducir a ellos otro lenguaje en ${\sf P}$ al enviarlos al aceptar o no aceptar?

Como no hay cadenas en , cualquier máquina que lo calcule siempre rechaza, por lo que no podemos asignar ninguna instancia de Sí a otros problemas. Del mismo modo para Σ ∗ no hay nada para asignar No-instancias.$\emptyset$$\Sigma^{\ast}$

Es necesario una reducción del polinomio del problema al problema B si quiere probar que B es "más duro" que A . Construimos una reducción polinomio mediante la transformación de cualquier instancia x de A en una instancia f ( x ) de B tal que x ∈ A si y sólo si f ( x ) ∈ B .$A$$B$$B$$A$$x$$A$$f(x)$$B$$x∈A$$f(x)∈B$

La función debe y puede ser polinomial. Si P = N P y A es un problema NP, entonces f puede por sí misma resolver el problema A del problema y embed cualquier x ∈ A en algún elemento y de B y cualquier x ∉ A en algún elemento z que no está en B .$f$$\mathsf{P}=\mathsf{NP}$$A$$f$$A$$x∈A$$y$$B$$x\notin A$$z$$B$

Si es o bien ∅ o Σ * a continuación, y o z no puede existir, de lo contrario el razonamiento anterior muestra que B es más duro que A .$B$$∅$$Σ^*$$y$$z$$B$$A$

Solo una nota: las respuestas anteriores están bien, sin embargo, no está muy lejos de la reducción trivial correcta:

si entonces cualquier L ∈ N P es Karp reducible al idioma { 1 } (solo mapee en tiempo polinómico cada x ∈ L a 1, cada x ∉ L a 0), que es trivialmente un lenguaje escaso$\sf{P} = \sf{NP}$$L \in \sf{NP}$$\{1\}$$x \in L$$x \notin L$

La dirección inversa: "si un lenguaje completo es Karp reducible a un conjunto disperso, entonces P = N P " es ciertamente más interesante y se conoce como el teorema de Mahaney :$\sf{NP}$$\sf{P}=\sf{NP}$

Supongamos que sea ​​una constante y que A se establezca de manera que para todo n , A tenga como máximo n c cadenas de longitud n . Si A es N P -Complete entonces P = N P .$c$$A$$n$$A$$n^c$$n$$A$$\sf{NP}$$\sf{P}=\sf{NP}$