Wenn P = NP, warum nicht

Offenbar , wenn , alle Sprachen in P mit Ausnahme von ∅ und Σ * wäre N P -komplette.${\sf P}={\sf NP}$${\sf P}$$\emptyset$$\Sigma^*$${\sf NP}$

Warum gerade diese beiden Sprachen? Können wir keine andere Sprache in auf sie reduzieren, indem wir sie ausgeben, wenn wir akzeptieren oder nicht akzeptieren?${\sf P}$

Da es in keine Zeichenketten gibt , lehnt jede Maschine, die sie berechnet, immer ab, sodass wir keine Ja-Instanz anderer Probleme auf irgendetwas abbilden können. Ähnliches gilt für Σ * gibt es nichts zu No-Instanzen abzubilden.$\emptyset$$\Sigma^{\ast}$

Sie benötigen eine Polynomreduktion von Problem zu Problem B , um zu beweisen, dass B "härter" als A ist . Wir bauen ein Polynom Reduktion durch jede Instanz Umwandlung x von A in eine Instanz f ( x ) von B , so dass x ∈ A iff f ( x ) ∈ B .$A$$B$$B$$A$$x$$A$$f(x)$$B$$x∈A$$f(x)∈B$

Die Funktion muss und kann polynomisch sein. Wenn P = N P und A ein NP-Problem ist, kann f selbst das Problem A des Problems lösen und x ∈ A in ein Element y von B und x ∉ A in ein Element z einbetten , das nicht in B ist .$f$$\mathsf{P}=\mathsf{NP}$$A$$f$$A$$x∈A$$y$$B$$x\notin A$$z$$B$

Wenn entweder ∅ oder Σ * dann y oder z nicht existieren kann, da sonst die Argumentation oben zeigt , dass B härter ist als A .$B$$∅$$Σ^*$$y$$z$$B$$A$

Nur eine Anmerkung: Die vorherigen Antworten sind in Ordnung, aber Sie sind nicht zu weit von der korrekten trivialen Reduktion entfernt:

wenn dann ist jedes L ∈ N P Karp reduzierbar auf die Sprache { 1 } ( ordnen Sie einfach alle x ∈ L zu 1, alle x ∉ L zu 0 in Polynomzeit zu), was trivialerweise eine spärliche Sprache ist$\sf{P} = \sf{NP}$$L \in \sf{NP}$$\{1\}$$x \in L$$x \notin L$

Die umgekehrte Richtung: „Wenn eine vollständige Sprache ist Karp reduzierbar auf eine dünne Menge dann P = N P “ ist sicher interessanter und es ist bekannt als die Mahaney Theorem :$\sf{NP}$$\sf{P}=\sf{NP}$

Lassen Sie eine Konstante sein und A so eingestellt werden , dass für alle n , A höchstens hat n c Strings der Länge n . Wenn A ist N P -Complete dann P = N P .$c$$A$$n$$A$$n^c$$n$$A$$\sf{NP}$$\sf{P}=\sf{NP}$