Diskussion:NP-Äquivalenz

Was bedeutet NP-leicht? Wo kann ich etwas über NP-Äquivalenz nachlesen? Wenn das irgendwas mit NP zu tun hat, dürfte der Speicheraufwand kaum "in astronomische Dimensionen" wachsen, sondern polynomial sein. -- Tian 20:57, 25. Feb 2005 (CET)

---

Ich glaube wir müssen hier entweder noch die Definition von NP-schwer anpassen, oder die von NP-Äquivalenz... --Koethnig 12:16, 5. Okt 2006 (CEST)

NP = ?

wofür steht NP? negativ, positiv? weshalb die Abkürzung? Markus, --203.147.0.44 11:29, 21. Jun. 2007 (CEST)

Nichtdeterministisch Polynomiell, siehe hier -- Mathias bla? 13:16, 21. Jun. 2007 (CEST)

Grundsatzfrage

Laut NP-Vollständigkeit#NP-Äquivalenz soll der hier beschriebene Begriff auch für Optimierungsprobleme anwendbar sein. Nun frage ich mich: Gegeben ein Lösungsvorschlag, wie soll dann in polynomieller Zeit überprüft werden, ob dieser wirklich das Optimum ist? Mir fällt nichts anderes ein, als alle Lösungen durchzugehen und zu schauen, ob wirklich keine optimaler ist. Das ist aber i.A. nicht in polynomieller Zeit lösbar. Heisst das mit andern Worten, dass Optimierungsprobleme per definitionem nie np-äquivalent sein können? Viel wahrscheinlicher: Ich blick wohl nicht durch. Die Antwort, die mir hier helfen könnte, hätte ja vielleicht auch eine Berechtigung, gleich in den Artikel eingearbeitet zu werden. --Chiccodoro 09:01, 12. Dez. 2007 (CET)

Erstmal: „optimal“ lässt sich nicht steigern. :-) Zur Transformation auf das Optimierungsproblem: bei einem NP-Entscheidungsproblem lässt sich per Definition von NP die Ja-Antwort in polynomialer Zeit überprüfen. Wenn Du für die Zielfunktion des entsprechenden Optimierungsproblems eine obere und eine untere Schranke kennst (das ist fast immer trivial möglich), kannst Du eine binäre Suche zwischen diesen beiden Werten durchführen und in jedem Schritt fragen: gibt es eine Lösung mit Wert höchstens sounsoviel (bei einem Minimierungsproblem)? Damit kannst Du das Optimierungsproblem polynomial lösen, sobald das Entscheidungsproblem polynomial lösbar ist, und andersherum sowieso. Anders ausgedrückt: ein Optimierungsproblem ist genau dann NP-äquivalent, wenn das zugehörige Entscheidungsproblem NP-vollständig ist. Hilft Dir das weiter? -- Sdo 23:33, 13. Dez. 2007 (CET)

Danke. Ich glaube, ich kann deine Erläuterung verstehen. Nach ein bisschen nachforschen habe ich festgestellt, dass ich einmal mehr in die selbe Falle getreten bin: Ich kannte den Unterschied zwischen terministisch und nicht-teterministisch nicht mehr. Der Haken liegt immer darin, dass bisher niemand beweisen konnte, dass NP-Probleme von einem Computer nicht in polynomieller Zeit gelöst werden können, und deshalb immer die Rede davon ist, dass sie von einer Nichtdeterministischen Turingmaschine in polynomieller Zeit lösbar sind. Ich fragte mich, wie z.B. beim Handelsreisenden in polynomieller Zeit entschieden werden soll, ob eine Lösung optimal ist. Wenn man das könnte, wäre also auch das Optimierungsproblem in polynomieller Zeit lösbar, und P=NP ... Stimmts? --Chiccodoro 11:35, 14. Dez. 2007 (CET)

Ja. -- Sdo 11:42, 14. Dez. 2007 (CET)

Zusammenlegung der Artikel NP-leicht und NP-Äquivalenz

Da beide Artikel nur aus wenigen Sätzen bestehen, der Begriff 'NP-leicht' auschließlich von diesem Artikel aus verlinkt wird und keiner der beiden mit Quellen belegt wurde, schlage ich vor die Artikel NP-leicht und NP-Äquivalenz zusammen zu legen. Sollte es keine Gegengründe geben, werde ich dies demnächst in Angriff nehmen.

-- 84.19.199.179 12:54, 11. Mai 2013 (CEST)

Ich bin für Löschen beider Artikel - die Begriffe sind kaum gebräuchlich - es gibt dazu keine Quellen. --Graf Alge (Diskussion) 17:16, 22. Okt. 2013 (CEST)