Si P = NP, pourquoi

Apparemment, si , toutes les langues de exception de et seraient terminées.P ∅ Σ ∗ N ${\sf P}={\sf NP}$${\sf P}$$\emptyset$$\Sigma^*$${\sf NP}$

Pourquoi ces deux langues en particulier? Ne pouvons-nous pas leur réduire une autre langue en en les sortant lors de l'acceptation ou de la non-acceptation?${\sf P}$

Comme il n'y a pas de chaînes dans $\emptyset$ , toute machine qui la calcule rejette toujours, donc nous ne pouvons pas mapper l'instance Oui d'autres problèmes à quoi que ce soit. De même pour $\Sigma^{\ast}$ il n'y a rien à mapper sur No-instances.

Vous avez besoin d' une réduction polynomiale du problème $A$ au problème $B$ si vous voulez prouver que $B$ est « plus difficile » que $A$ . On construit une réduction polynomiale en transformant toute instance $x$ de $A$ dans une instance $f(x)$ de $B$ tel que $x∈A$ ssi $f(x)∈B$ .

La fonction doit et peut être polynomiale. Si P = N P et A est un problème NP, alors f peut lui - même de résoudre le problème A du problème et d' intégration tout x ∈ A dans un élément y de B et tout x ∉ A dans un élément z qui ne sont pas dans B .$f$$\mathsf{P}=\mathsf{NP}$$A$$f$$A$$x∈A$$y$$B$$x\notin A$$z$$B$

Si est soit ∅ ou alors ou ne peut pas exister, sinon le raisonnement ci - dessus montre que est plus difficile que .$B$$∅$ yzB$Σ^*$$y$$z$$B$$A$

Juste une note: les réponses précédentes sont correctes, mais vous n'êtes pas trop loin de la réduction triviale correcte:

si alors tout est Karp réductible à la langue (il suffit de mapper en temps polynomial tous les à 1, tous les à 0), qui est trivialement un langage clairsemé L ∈ N P { 1 } x ∈ L x ∉ $\sf{P} = \sf{NP}$$L \in \sf{NP}$$\{1\}$$x \in L$$x \notin L$

La direction inverse: "si un langage complet est Karp réductible à un ensemble clairsemé alors " est certainement plus intéressant et il est connu comme le théorème de Mahaney :P = N $\sf{NP}$$\sf{P}=\sf{NP}$

Soit une constante et fixé de telle sorte que pour tout , ait au plus chaînes de longueur . Si est terminé, alors .A n A n c n A N P P = N $c$$A$$n$$A$$n^c$$n$$A$$\sf{NP}$$\sf{P}=\sf{NP}$