Diskussion:NP (Komplexitätsklasse)
aus Wikipedia, der freien Enzyklopädie
[Bearbeiten] die Definition ist falsch
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 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)
[Bearbeiten] CoNP fehlt auch.
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. :-)
[Bearbeiten] Unverstaendlich
"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)
