Diskussion:NP (Komplexitätsklasse)
Begriffliches Problem[Quelltext bearbeiten]
Meine Anmerkung ist nicht so wichtig, allerdings hat mir die Formulierung "das schwierigste Problem" zu Beginn der Ausführungen nicht gefallen. Es ist doch gerade entscheidend, dass alle NP-vollständigen Probleme im Grunde genommen gleich schwer sind. ==Horstmeier 12:57, 24. Nov. 2007 (CET)
die Definition ist falsch[Quelltext bearbeiten]
Es stimmt nicht, dass NP-Probleme von NDT nur "akzeptiert" werden müssen. Für jedes NP-Problem gibt es eine nichtdeterministische TM die in bezüglich der Eingabe polynomieller Zeit anhält und das Problem entscheidet. Die NDT ist schlie´ßlich so definiert, dass sie nicht akzeptiert, wenn kein akzeptierender Bereschnugsweg existiert.
"Es gibt noch eine zweite äquivalente Definition von NP, als die Menge aller Probleme, deren Lösung von einer deterministischen Turingmaschine in polynomialer Zeit verifiziert werden können."
Das ist doch Unsinn, denn das ist doch die Komplexitätsklasse P.
- Nein, es geht hier nur um die Verifikation der Lösung, nicht um das Finden! Wenn ich eine Belegung für SAT bekomme, kann ich natürlich in polynomieller Zeit feststellen, ob sie erfüllend ist oder nicht. Beide Aspekte (schwieriges Finden und einfaches Überprüfen) gehören zur Definition von NP. --Pinguin.tk 11:20, 10. Dez 2004 (CET)
- Die Probleme in P können von einer DTM nicht nur als positiv verifiziert, sondern auch allgemein akzeptiert werden. Ich habe mal beide formalen Definitionen und eine Skizze des Äquivalenzbeweises zum Artikel hinzugefügt. --Mstigge 12:30, 13. Mär. 2008 (CET)
Die Definitionen hören sich wirklich so an als wären es Definitionen für P. NP enthält ja genau die Probleme die _nicht_ in polynomialer Zeit gelöst werden können. Ist NP wirklich so gedacht das es auch P enthält? Ich hatte das jetzt anders in Erinnerung, aber könnt schon sein. --(Der vorstehende, nicht signierte Beitrag stammt von 84.56.245.91 (Diskussion • Beiträge) 18:21, 8. Mär. 2007)
- Ja das ist so. was von einer TM berechnet werden kann genauso auch von einer NTM berechnet werden. --Spid 17:41, 9. Mär. 2007 (CET)
- Zumal die Frage, ob die Probleme in NP in (deterministisch) polynomieller Zeit gelöst werden können oder nicht, gerade das P=NP Problem ist. --Mstigge 12:04, 13. Mär. 2008 (CET)
- Das 'N' in NP steht nicht für nicht polynomiell, sonder für nicht deterministisch (bzgl der TM). --Doktorhase 21:18, 21. Feb. 2010 (CET)
CoNP fehlt auch.[Quelltext bearbeiten]
Die Klasse CoNP ist nicht erwähnt. Dies sind Probleme, die deterministisch in polynomieller Zeit falsifiziert werden können. Formal ist es die Menge aller Sprachen, deren Komplementsprachen in NP vorhanden sind. Ferner gilt, wenn P=NP gilt, dass CoNP=NP. Sobald ich Zeit habe, werde ich dies in den Artikel einfließen lassen oder gar einen neuen Artikel CoNP schreiben. Wer dazu eher Gelegenheit hat, darf das auch früher tun. :-)
- For the record: Steht inzwischen im Artikel. --Mstigge 12:32, 13. Mär. 2008 (CET)
Unverstaendlich[Quelltext bearbeiten]
"Es gibt noch eine zweite äquivalente Definition von NP als die Menge aller Probleme, für die es, wenn die Antwort ja lautet, einen entsprechenden Beweis (Zertifikat) gibt, dessen Länge durch ein Polynom in der Länge des Problems beschränkt ist, und der von einer deterministischen Turingmaschine in polynomialer Zeit verifiziert werden kann."
Laesst sich das auch in kuerzeren Saetzen sagen? Welche Frage war die mit der Antwort "ja"? Und was war jetzt die Definition? Ich versteh da leider gar nichts.
- Irgendwer hat da meine ursprüngliche Formulierung ausgebaut... Gemeint ist, daß NP die Menge der Probleme ist, bei denen man in polynominaler Zeit überprüfen kann, ob eine geratene Lösung tatsächlich eine Lösung ist oder nicht. -- MlaWU 17:24, 16. Mai 2005 (CEST)
NP Vollständig oder effizient lösbar[Quelltext bearbeiten]
mir gefällt diese formulierung "Viele Probleme, die in der Komplexitätsklasse NP liegen, insbesondere die NP-vollständigen, lassen sich vermutlich nicht effizient lösen" nicht... vor allem die formulierung "insbesondere die NP-vollständigen" ist humbug
ich meine NP zerfällt doch (vermutlich) in P und NPC (die NP Vollständigen Probleme) - die Probleme aus NP sind damit entweder effizient lösbar oder NP-Vollständig... wenn wir mal die klassen FPT und W[1] und W[2] hinzunehmen, dann könnte man sagen, dass viele instanzen NP Vollständiger Probleme effizient lösbar sind, aber (vermutlich) nicht allgemein... da sollte man das zumindest präziser formulieren
AlgorithMan 01:44, 26. Jan. 2008 (CET)
- NP zerfällt vermutlich nicht in P und NPC... vielmehr ist NP≠(P u NPC) falls P≠NP. vgl. die Illustration bei P-NP-Problem --88.66.254.201 19:01, 23. Feb. 2008 (CET)
Fehler bei der "Suchproblem-Definition"?[Quelltext bearbeiten]
Es steht dort dass R_L von einer DTM erkannt werden muss, aber muss diese nicht auch polynomielle Laufzeit haben?(nicht signierter Beitrag von 62.224.195.96 (Diskussion | Beiträge) 15:27, 7. Feb. 2009 (CET))
Problem mit dem Beispiel[Quelltext bearbeiten]
Alle Zahlen von 1 bis e^n ? Das könnte schwierig werden, da die größtenteils wie e^n selbst in R liegen. Wäre da nicht 1 bis z.B. 5^n besser? (nicht signierter Beitrag von 141.83.146.111 (Diskussion | Beiträge) 15:48, 6. Mai 2010 (CEST))
- Ja, habs geändert. --Euku:⇄ 20:25, 6. Mai 2010 (CEST)
echte Teilmengenbeziehung[Quelltext bearbeiten]
Mag das mal jemand für "Nicht-Informatiker" umformulieren oder etwas erläutern? Vielleicht so?
Meist sind für Beziehungen zwischen Komplexitätsklassen nur Inklusionsrelationen bekannt. Nicht bekannt ist, ob jeweils eine echte Teilmengenbeziehung gilt, d.h. die Klassen neben der enthaltenen Klasse noch weitere Elemente enthalten.