Ich habe ein Bild gesehen, das die Beziehungen von P, NP, NP-Hard und NP-Complete beschreibt, die so aussehen:
https://en.wikipedia.org/wiki/NP-hardness#/media/File:P_np_np-complete_np-hard.svg
Ich frage mich, ob Folgendes möglich ist? Was bedeutet, P = NP, aber nicht alle von ihnen sind in NP-Hard:
Bearbeiten: Ich möchte Folgendes hinzufügen: Ich bin nicht hier, um zu sagen, ob das Originalbild falsch oder richtig ist. Ich bin nur hier, um eine Frage zu stellen, ob mein Bild eine mögliche Situation enthält. Mit anderen Worten, ist es richtig anzunehmen, dass alle 3 Bilder möglich sind?
np-complete
np-hard
np
Frank
quelle
quelle
Antworten:
Eigentlich ist deine Version korrekt und die von Wikipedia ist falsch! (Außer dass es unten einen winzigen Haftungsausschluss gibt.)
Wenn , Wikipedia behauptet , dass jedes Problem in ist -komplette. Dies ist jedoch nicht der Fall: in der Tat, jedes Problem in wäre -komplette, mit Ausnahme der trivialen Sprachen und .P=NP P NP P NP ∅ Σ∗
Sie können keine nicht leere Sprache auf reduzieren , da bei einer Reduktion von vielen "Ja" -Instanzen von auf "Ja" -Instanzen von , jedoch keine "Ja" -Instanzen hat. Ebenso können Sie nicht auf reduzieren, da es nichts gibt, dem Sie die "Nein" -Instanzen zuordnen können. Wenn jedoch , dann ist jede andere Sprache in ist -komplette, da Sie die Sprache , in der Reduktion zu lösen.L ∅ L ∅ ∅ Σ∗ P=NP P NP
Um es explizit zu machen:
quelle