Wenn ein Problem X (Entscheidungsproblem) als NP-Complete bekannt ist und nachweislich auf das Problem Y in Polynomialzeit reduziert ist, können Sie dann sagen, dass das Problem Y NP-Complete ist?Wenn ein Problem X (Entscheidungsproblem) als NP-Complete bekannt ist und nachweislich auf das Problem Y reduziert ist, können Sie dann sagen, dass das Problem Y NP-Complete ist?
Mein erster Gedanke war, nein, Problem Y muss gezeigt werden, dass es in NP ist. Aber nach weiterem Nachdenken, wenn X auf Y reduziert wird, wird Y bereits als NP-vollständig betrachtet. Jetzt bin ich nur verwirrt ... jede Hilfe wäre willkommen.
Ich denke, du hattest es das erste Mal. Wenn wir ein bekanntes Problem auf ein anderes NP-vollständiges Problem reduzieren können, ist dieses Problem auch NP. – Jim
aus dem Wiki: "... es wurde gezeigt, dass Tausende von anderen Problemen NP-vollständig sind, indem sie von anderen Problemen, die zuvor als NP-vollständig erkannt wurden, reduziert wurden ..." so würde ich sagen "Ja" ist die Antwort? –
Per Definition ist Y "NP-schwer". Ein NP-schweres Problem ist eines, das verwendet werden kann, um jedes Problem in NP zu lösen, einschließlich NP-vollständiges Problem. Ein NP-schweres Problem besteht jedoch nicht notwendigerweise in NP. – gnasher729