Diskussion:NP-Vollständigkeit
aus Wikipedia, der freien Enzyklopädie
Bei den standard Np-vollständigen Problemen wurde Bin Packing mit BPP abgekürzt. Das beißt sich meiner Meinung nach ein wenig mit der Abkürzung von der Komplexitätsklasse bounded-error propabilistic polynomial time.
worum gehts hier? --'~'
- Um eine Problemklasse: Eben die Klasse der NP-vollstaendigen Probleme. Man glaubt, dass diese Klasse sehr schwierige Probleme enthaelt (was die Loesung durch Rechner betrifft.) --pintman 20:22, 26. Jul 2003 (CEST)
-
- Das könnte man auch reinschreiben, finde ich. --'~' 23:27, 26. Jul 2003 (CEST)
- Ja finde ich auch. der einstieg ist echt doof. -- Horst Frank 02:12, 13. Nov 2003 (CET)
??? Bin zwar Informatiker habe aber trotz der Erklärung hier nichts verstanden. Rat 16:15, 17. Okt 2003 (CEST)
-
- Dann bist Du sicher kein guter Informatiker... (oder ganz am Anfang der Ausbildung dazu). --Coma 02:42, 13. Nov 2003 (CET)
hi coma! wollte mich als NichtInformatiker grade an eine einleitung machen ... noch mal gutgegangen -- Horst Frank 03:30, 13. Nov 2003 (CET)
- Ich hoffe es ist jetzt besser, aber ich bin nicht umhingekommen mit fachbegriffen um mich zu werfen, dürfte für einen laien also auch nicht verständlicher sein. daher noch die anmerkung ganz oben... --Coma 03:54, 13. Nov 2003 (CET)
http://en.wikipedia.org/wiki/NP-complete scheint IMHO leichter verständlich zu sein.--'~' 11:56, 17. Feb 2004 (CET)~
- Ich bin gegen Übersetzungen aus der englischen Wikipedia. Sie sollte vielmehr dem Vergleich für Nutzer dienen, damit er mehrere Quellen hat, statt von dort laienhaft zu übersetzen. Dazu sind allenfalls fachlich ausgebildete Übersetzer befähigt. Vorschlag: Wenn umformulieren, dann Quellen Dritter heranziehen. Ich wollte mich in den nächsten Wochen aber eh mit NP-Vollständigkeit auseinandersetzen, vgl. Wikipedia:WikiProjekt Wirtschaftsinformatik Stern 12:05, 17. Feb 2004 (CET)
Vielleicht könnte man noch auf NP-Härte eingehen (eigener Artikel) und die Definiton darauf aufbauen. Dann kann der Laie nachschlagen, was momentan noch nicht möglich ist und der Profi langweilt sich nicht. Was denkt Ihr? Stern 22:17, 21. Feb 2004 (CET)
Ich versuch schon den ganzen Abend, diesen Artikel zu verstehen (damit ich ein bisschen mitarbeiten kann) und häng immer noch beim ersten Absatz :)
"(...) (also zu der Klasse von Problemen zu gehören, für die eine nichtdeterministische Turingmaschine existiert, die das Problem in Polynomialzeit löst)"
Bei diesem Satz ist mir die nicht-deterministische Turingmaschine schon zu hoch, aber ich vermute (anhand zu diesem Thema gefundener Texte), dieses Thema ist etwas komplexer. Aber was mich beschäftigt, wie kann man bei einem nicht-deterministischem Algorithmus vorhersehen, dass er in Polynomialzeit läuft? --brunft 20:38, 12. Mär 2004 (CET)
- Unter bestimmten Bedingungen geht dass.
- Das ist je nach Definition nicht nötig, manchmal reicht auch, dass es einen Fall gibt, bei dem er nach Polynomialzeit hält.
--Coma 21:17, 12. Mär 2004 (CET)
- Es geht hierbei nur darum, dass die nichtdeterministische Turingmaschine in einem der Fälle endet. Wenn Du nichtdeterministisch in diesem Zusammenhang nochmal erklärt haben willst, ruhig nochmal nachfragen. Stern 20:43, 12. Mär 2004 (CET)
Inhaltsverzeichnis |
[Bearbeiten] Reduktion
"NP-vollständige Probleme zeichnen sich nun dadurch aus, selbst in der Menge der NP-Probleme zu liegen, andererseits aber jedes Entscheidungsproblem in dieser Klasse in Polynomialzeit (mit einer deterministischen Turingmaschine) auf dieses reduziert werden kann."
Kann jemand den Satz so umformulieren (oder ergänzen), dass er einen Sinn ergibt? thx
- naja, die Idee ist folgende: einerseits sind die NP-vollständigen Probleme NP-hart, d.h. sie sind "mindestens so schwer wie etwas, das eine nichtdeterministische Turingmaschine (TM) in polynomieller Zeit lösen kann". Da gibt's aber noch ne ganze Menge anderer Probleme, deshalb die zweite Bedingung für die Vollständigkeit: sie liegen auch tatsächlich in NP, d.h. man kann einen Algorithmus für eine nichtdeterministische TM finden, der das Problem tatsächlich löst. Praktisch gesehen beweist man NP-Vollständigkeit aber oft so, dass man den "mindestens so schwierig"-Teil mittels Reduktion ausführt, d.h. man transformiert das Problem, das man gerade vorliegen hat, in ein anderes Problem, von dem man weiß, dass es NP-hart ist (z.B. SAT). Dieses Transformieren wird als Reduktion bezeichnet, und zwar muss diese Reduktion in Polynomialzeit durchführbar sein. Warum? Man kann NP-vollständige Probleme in Exponentialzeit lösen (also asymptotische Laufzeit 2^n für ein Problem der Größe n). Wenn nun die Reduktion schon exponentiell viel Zeit verbrauchen würde, dann könnte ich möglicherweise damit das Problem so stark vereinfachen, dass der nun noch zu lösende Teil sehr einfach ist. Um diese "Vereinfachung" zu verhindern, muss man sicherstellen, dass die Reduktion in polynomieller Zeit abläuft.
- Das tolle an den NP-vollständigen Problemen ist nun, dass man durch diese Reduktion folgendes weiß: Falls ich eines von ihnen "schnell" (in polynomieller Zeit) lösen kann, dann kann ich das mit allen, eben durch Anwendung der Reduktion. Siehe auch [P-NP Problem]].
- werde den Artikel bei Gelegenheit überarbeiten... --Pinguin.tk 23:17, 21. Jun 2004 (CEST)
[Bearbeiten] Polynomialzeit
Ach ja, 'Polynomailzeit-Algorithmus' und 'polynomieller Algorithmus' bezeichnen das Gleiche, richtig? Können wir uns auf eine Form des Begriffs einigen? --brunft 12:56, 13. Mär 2004 (CET)
- ja, das ist hauptsächlich eine Frage der Gewohnheit. In der Literatur findest Du diese und zahlreiche andere Varianten... --Pinguin.tk 23:14, 21. Jun 2004 (CEST)
[Bearbeiten] PCP
Das Postsche Korrespondenzproblem gehört hier nicht hin, es ist in der Standardversion ein Beispiel für ein unentscheidbares Problem. Starblue 22:53, 28. Mär 2004 (CEST)
- Damit dürfte das aber auch mindestens NP-schwer sein :-)))) -Coma 18:16, 29. Mär 2004 (CEST)
- aber eben nicht NP-vollständig! --Pinguin.tk 23:02, 21. Jun 2004 (CEST)
[Bearbeiten] Leichte Konstruktion nicht praxisrelevanter Beispiele?
Ist es wirklich wahr, dass sich leicht ein kaum praxisrelevantes NP-vollständiges Problem konstruieren läßt? Ich höre das hier zum ersten mal. Ich denke, auch eine Reduktion auf ein nicht praxisrelevantes Problem wäre einfacher gewesen als Cooks direkter Beweis. Ich bitte um Quellen oder Angabe der Konstruktion. --Tian 16:33, 12. Okt 2004 (CEST)
Ah, vielleicht war die Sprache der Paare (M,x) gemeint, wobei M die Kodierung einer standardisierten polynomialzeitbeschränkten nichtdeterministischen TM ist, die x akzeptiert. (Standardisiert bedeutet dabei in formalisierter Form, dass man die Polynomialzeitbeschränkung leicht nachprüfen kann.) Cook hat im wesentlichen diese Sprache auf SAT zurückgeführt, aber mir scheint, diese Sichtweise ist neuer. Cook hat meiner Meinung nach anders als es die Formulierung des Artikels nahelegt als erster gezeigt, dass es überhaupt NP-vollständige Probleme gibt. -- Tian 16:46, 28. Feb 2005 (CET)
- Ja, Cook hat als erster die Existenz gezeigt! Aber das ist ja häufig so, dass man einfachere Beweise erst später findet. --Coma 02:57, 1. Mär 2005 (CET)
