Wenn P = NP, warum nicht

15

Offenbar , wenn , alle Sprachen in P mit Ausnahme von und Σ * wäre N P -komplette.P=NPPΣ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?P

David Faux
quelle

Antworten:

25

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.Σ

Luke Mathieson
quelle
4

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 .ABBAxAf(x)BxAf(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 .fP=NPAfAxAyBxAzB

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

jmad
quelle
3

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 istP=NPLNP{1}xLxL

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 :NPP=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 .cAnAncnANPP=NP

Vor
quelle