Diskussion:NP-Vollständigkeit

Diese Diskussionsseite dient dazu, Verbesserungen am Artikel „NP-Vollständigkeit“ zu besprechen. Persönliche Betrachtungen zum Thema gehören nicht hierher. Für allgemeine Wissensfragen gibt es die Auskunft.

Füge neue Diskussionsthemen unten an:

Klicke auf Abschnitt hinzufügen, um ein neues Diskussionsthema zu beginnen.

• Diskussionsregeln
• Hilfe zu Diskussionsseiten
• Sei sachlich und freundlich!
• Greife niemanden persönlich an!
• Geh von guten Absichten aus.

Zum Archiv

Wie wird ein Archiv angelegt?

Automatische Archivierung

Auf dieser Seite werden Abschnitte halbmonatlich automatisch archiviert, wenn sie mit {{Erledigt|1=--~~~~}} markiert sind. Um die Diskussionsseite nicht komplett zu leeren, verbleibt mindestens ein Abschnitt.

Dies und das

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.

--Juan Gamnik

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)

1. Unter bestimmten Bedingungen geht dass.
2. 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)

---

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)

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)

Polynomialzeit ist etwas genauer, denn es gibt auch noch parallel die Betrachung nach dem Platzbedarf, analog Polynomialplatz-Algorithmus --TheReincarnator (Diskussion) 11:40, 26. Aug. 2012 (CEST)

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)

...aehm...

Ich dachte NP-Vollstaendigkeit haette sich als unentscheidbar herausgestellt? --Gulbulman 05:50, 24. Aug. 2008 (CEST)

Unentscheidbarkeit ist etwas völlig anderes als Komplexitätsklassen. Das Halteproblem ist unentscheidbar, TSP-Entscheidungsproblem ist in NPC. Vielleicht meinst du das P-NP-Problem. Allerdings hat sich da auch noch nichts weiter ergeben. --MartinThoma 07:18, 15. Dez. 2011 (CET)

NP != P

Der Beweis wurde von Vinay Deolalikar vorgelegt. Er muss jetzt nochg geprüft werden.

http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf (nicht signierter Beitrag von 194.77.48.125 (Diskussion) 10:47, 16. Aug. 2010 (CEST))

"Nur noch" ist gut. So ein Review-Prozess dauert recht lange. Außerdem gibt es viele "Beweise", dass P != NP (oder auch P = NP) ist. Ich habe hier schon mal einen Blog, der an der Korrektheit zweifelt. Auf Stackoverflow steht etwas mehr dazu. --MartinThoma 07:22, 15. Dez. 2011 (CET)

Sprachen

NP-Vollständigkeit zeichnet spezielle formale Sprachen der Komplexitätsklasse NP aus. So werden solche Sprachen NP-vollständig genannt, die – intuitiv gesprochen – die vollständige Schwierigkeit aller Sprachen aus der Komplexitätsklasse NP in sich tragen.

Schön. Hat auch jemand ein Beispiel für so eine spezielle Sprache oder gar die Sprache von Cook? Der Artikel über formale Sprachen enthält nirgends die magischen Buchstaben "NP", geschweige denn irgendeinen Hinweis auf diesen Artikel oder sonst was. Was soll uns also dieser Absatz sagen? Wäre nett, wenn sich da jemand fachkundiges annehmen könnte und den Text entsprechend klarstellt. Danke :) --84.147.42.85 21:59, 22. Jun. 2011 (CEST)

Es gibt zum einen die Liste von Komplexitätsklassen und NP (Komplexitätsklasse).

Was verstehst du unter der "Sprache von Cook"? Das Erfüllbarkeitsproblem der Aussagenlogik (SAT)?

Ein kleiner Hinweis: Für die Komplexitätstheorie sind formale Sprachen und Probleme etwa das gleiche.

Beantwortet das deine Frage? --MartinThoma 07:29, 15. Dez. 2011 (CET)

Satzstellung "überhaupt gibt"

Im Artikel steht der Satz

"Die wesentliche Leistung von Cook bestand zunächst darin, den Nachweis erbracht zu haben, dass es ein NP-vollständiges Problem überhaupt gibt."

Ich habe den Satz korrigiert zu

"Die wesentliche Leistung von Cook bestand zunächst darin, den Nachweis erbracht zu haben, dass es überhaupt ein NP-vollständiges Problem gibt."

ʘx hat die Änderung rückgängig gemacht, weil er die alte Version für "sprachlich besser" halte.

Daher hier nun die Erläuterung der Bedeutung des Satzes. Bei der alten Version bezieht sich das Adverb "überhaupt" direkt auf das Verb "gibt", womit die Betonung also auf die Existenz gelegt wird eines nicht näher benannten NP-vollständigen Problems. Das bedeutet, dass der Satz aussagt, dass Cook für irgendein NP-vollständiges Problem gezeigt habe, dass dieses Problem existiere. Der Satz beinhaltet nicht, dass es vorher keine Existenzbeweise anderer NP-vollständiger Probleme gegeben habe, sondern betont stattdessen die Schwierigkeit, die Existenz diesen einen NP-vollständigen Problems zu zeigen.

In der korrigierten Version bezieht sich das Adverb "überhaupt" auf das Objekt "ein NP-vollständiges Problem". Es betont also, dass Cook gezeigt hat, dass das Verb des Satzes (geben) auf mindestens ein NP-vollständiges Problem angewendet werden kann, dass er also als Erster die Existenz eines NP-vollständigen Problemes nachweisen konnte.

Ich bin mir sicher, dass die Intention hinter dem Satz der der korrigierten sprachlichen Version entspricht. -- Arno Nymus (Diskussion) 04:20, 23. Mär. 2012 (CET)

Adverbien beziehen sich niemals auf Substantive, es bezieht sich dann eher auf den ganzen Rest (meinem Sprachverständnis zufolge). Naja, egal, deine Version gefällt mir jedenfalls besser. --Chricho ¹ ² 09:07, 23. Mär. 2012 (CET)

Dein Vorschlag löst das von dir genannte Problem nicht. Schau dir deine Version mal genau an: Sie ist *inhaltlich* identisch mit meiner, lediglich *sprachlich* finde ich sie schlechter. Man kann da ganz genauso auf die Idee kommen, Cook habe lediglich Existenz gezeigt.

Wenn du tatsächlich meinst, man müsste im Text deutlicher werden, dann kann man das meiner Ansicht nach nicht durch die Wortstellung lösen. Dann müsste da der Text ein wenig umgebaut werden. Ich habe im Text einen solchen Umbau vorgenommen. Das Wort "überhaupt" kommt zwar noch vor, jedoch sollte es aufgrund der Formulierung nun kein Problem mehr darstellen. ʘχ (Diskussion) 10:01, 23. Mär. 2012 (CET)

Der Umbau macht es etwas deutlicher, ändert aber nichts an der grundlegenden Frage. Natürlich kann man inhaltliche Betonung über sprachliche Mittel herstellen und darüber deutlicher machen, was der zentrale Aspekt eines Satzes ist (s.o.). Ich habe ja bereits dargelegt, was für meine Version spricht (danke auch an Chricho für die Anmerkung dazu). @ʘχ: Könntest Du bitte darlegen, *wieso* Du die alte Version besser findest? -- Arno Nymus (Diskussion) 11:43, 23. Mär. 2012 (CET)

Das verstehe ich nicht, da die aktuelle Fassung das von dir genannte Problem löst. Wo bzw. warum siehst du jetzt noch Änderungsbedarf? ʘχ (Diskussion) 13:54, 23. Mär. 2012 (CET)

Der zusätzliche Satz über SAT lässt den Leser zwar eher erahnen, was der zentrale Punkt ist als vorher. Der darauf folgende Satzteil ", dass ein NP-vollständiges Problem überhaupt existiert" hat aber noch immer die von mir oben beschriebene Konnotation und läuft damit dem Sinn des Absatzes entgegen. Aus diesem Grunde besteht von mir logischerweise noch immer der Änderungswunsch, dass "überhaupt" hinter "dass" gesetzt werden sollte. Weiterhin bleibt meine Frage bestehen, was dagegen spricht bzw. genauer, "*wieso* Du die alte Version besser findest?" -- Arno Nymus (Diskussion) 14:27, 23. Mär. 2012 (CET)

Aktuell *soll* der Satz sagen, dass es bereits gereicht hätte, die NP-Vollständigkeit irgendeines Problems zu zeigen. Im folgenden wird dann ja ausgeführt, dass Cook aber mehr als das tat, nämlich ein besonders wichtiges Problem benutzte. Denn darauf will der Abschnitt ja hinaus. Das heißt, der Satz tut genau das, was er soll. Wenn man nun "überhaupt" woanders hinstellt, sagt er immer noch dasselbe, es ändert sich nichts.

Ich kann die Probleme, die du siehst, einfach nicht nachvollziehen. Der Satz über SAT gibt nicht nur eine "Ahnung", sondern sagt explizit, was der zentrale Punkt ist. "SAT ist NP-vollständig" ist ja genau der Inhalt des Papers! Der darauffolgende Satzteil ist nun nicht mehr missverständlich, denn weil auf SAT hingewiesen wurde, ist klar, dass Cook nicht nur die Existenz irgendeines Problems gezeigt, sondern auch eine Konstruktion geliefert hat. Das von dir genannte Problem ist damit gelöst. Meine Änderung enthält außerdem das Wort "bereits", welches nicht ignoriert werden darf.

Mathematisch ist es sogar nicht richtig, hier von einer "entgegenlaufenden Konnotation" zu sprechen, da die Aussage, Cook habe die NP-Vollständigkeit von SAT gezeigt, kein Widerspruch ist zu der Aussage, er habe die Existenz eines NP-vollständigen Problems gezeigt. Letzteres folgt aus ersterem (Beweis der Existenz durch Konstruktion, also keine Voraussetzung der Existenz), daher gibt es hier keine sich widersprechenden Aussagen.

Ich möchte wiederholen, dass dein Änderungsvorschlag *nichts* an der Missverständlichkeit der Ursprungsfassung ändert. Die Stellung von "überhaupt" im Satz hat keinerlei Einfluss auf die Missverständlichkeit, die von dir angenommene Bedeutungsänderung gibt es nicht. Das, was du möchtest, kannst du nicht durch Umstellen des Wortes "überhaupt" erreichen. Ich habe daher die Missverständlichkeit auf andere Weise gelöst.

Ich halte meine Variante für sprachlich etwas besser, weil so ein besserer Rhythmus im Satz entsteht, das heißt, die Lesbarkeit ist besser und angenehmer (bei *gleichem* Inhalt, wie ich nochmal betonen will). (Nur um sicher zu gehen, dass du keine merkwürdige Betonung des Satzes anwendest: In der üblichen Lesart liegt die Betonung nicht auf dem Wort "überhaupt", sondern auf "existiert".) ʘχ (Diskussion) 15:17, 23. Mär. 2012 (CET)

Ich muss in mehrerlei Hinsicht widersprechen:

1. Die Satzstellung und insbesondere die Position von Adverbien ist sehr wohl geeignet, die Semantik eines Satzes zu ändern. Das ist schlicht Fakt. In diesem Fall ändert die Position des "überhaupt" die inhaltliche Betonung, d.h. welcher Aspekt des Satzes für den Kontext dem Leser als der relevanteste präsentiert wird. Wenn Du der Meinung bist, dass diese inhaltliche Betonung egal ist und nur der reine Fakt der Aussage zählt, dann sollten wir das "überhaupt" komplett aus dem Satz rausnehmen, weil das "überhaupt" - an jeder Position - genau nur für eine (je nach Position unterschiedliche) inhaltliche Betonung sorgt (s.o.).
2. Es ist sehr wohl richtig, davon zu sprechen, dass die durch "überhaupt" dem Satz übertragene sprachliche Konnotation dem Sinn des Absatzes entgegenläuft. Entsprechend kann das Problem, das ich sehe, sehr wohl durch die von mir vorgeschlagene Änderung behoben werden. Im mathematischen Sinne sehe ich natürlich kein Problem mit den Sätzen. Dafür reicht es aber auch aus, dass die Aussagen der Sätze korrekt sind; den Sinnzusammenhang deckt das natürlich nicht ab.
3. Ich möchte an der Stelle auch darauf hinweisen, dass ich beim Umbau den zusätzlichen Satz über SAT als die Verbesserung empfinde. Die Einführung der weiteren Füllworte wie "Alleine" und "bereits" betrachte ich eher skeptisch für die Klarheit des Absatzes.
4. Die schlechte Lesbarkeit der alten Version des Satzes war überhaupt der Grund, warum ich darauf gekommen bin, dass der Satz geändert werden solle. Ich las den Artikel und kam bei dem Satz ins Stocken wegen dem eigenartig platzierten "überhaupt". Von mir aus können wir dazu andere Benutzer befragen, welche der beiden Alternativen sie als besser lesbar empfinden.

Alternativ kann man den Satz gerne auch ganz umformulieren, z.B. in die Richtung

"Die wesentliche Erkenntnis war, dass mindestens ein NP-vollständiges Problem existiert." -- Arno Nymus (Diskussion) 17:52, 23. Mär. 2012 (CET)

„sehr künstliche Sprachen“

„Heute existieren deutlich einfachere Nachweise für die Existenz solcher Probleme, allerdings sind die dafür verwendeten Sprachen sehr künstlich.“

Worauf bezieht sich dieser Satz? --Chricho ¹ ² 11:16, 23. Mär. 2012 (CET)

Erstes Kriterium in der Einleitung ist doch nicht falsch

Da war ich ja doch überrascht, in einem nicht gerade neuen Artikel eine falsche Definition zu finden: "ein deterministisch arbeitender Rechner nur polynomiell viel Zeit benötigt, um zu entscheiden, ob eine vorgeschlagene Lösung tatsächlich eine Lösung ist und"

Es muss heißen: "ein nichtdeterministisch arbeindender Rechner" (ich hab's nochmal verifiziert: Englische Wikipedia). Polynomiell viel Zeit wird noch als effizient (na gut, sagen wir: machbar) betrachtet, allerdings hier mit der Rahmenbedingung eines nichtdeterministischen Rechners, d.h. eines Rechners, der aus einer Menge möglicher nächster Rechenschritte den nächsten bestmöglichen Schritt "raten kann". Es ist möglich, statt zu raten, alle Möglichkeiten durchzuprobieren und somit zum bestmöglichen Schritt zu kommen, nur leider ist das ganze Durchprobieren exponentiell aufwändig, so dass man praktisch ewig warten kann. Ob's ne effizientere Möglichkeit gibt, als das exponentiell aufwändige Durchprobieren: darum dreht sich der ganze Zirkus der Forschung der Theoretischen Informatik darüber, ob P==NP oder P!=NP.

Ich passe das erste Kriterium jetzt entsprechend an. --DST (Diskussion) 00:29, 26. Sep. 2012 (CEST)

haha ... jetzt hab ich die Seite ändern wollen und da stand ein Kommentar, dass die Definition tatsächlich korrekt ist und nicht geändert werden soll. Und stimmt auch: ich habe nicht genau gelesen: es ging ja darum, eine vorhandene Lösung zu überprüfen, statt die Lösung zu finden. Das ist äquivalent. Ich ergänze daher noch die äquivalente Formulierung. --DST (Diskussion) 00:34, 26. Sep. 2012 (CEST)

Ich habe diese Änderung rückgängig gemacht, weil sie die Einleitung noch schwerer lesbar macht. Ich habe diese Einleitung geschrieben und versucht, sie so einfach wie möglich bei größtmöglicher Genauigkeit zu machen. Ich denke, die aktuelle Fassung ist ein ganz guter Kompromiss. ʘχ (Diskussion) 01:03, 26. Sep. 2012 (CEST)

wenn die jetzige version so verwirrend ist, waere es vielleicht angebracht, die definition von NP durch die andere zu ersetzen, die vielleicht eher den erwartungen entspricht. gibt es einen besonderen grund dafuer, gerade diese version zu verwenden? --Mario d 16:50, 26. Sep. 2012 (CEST)

• Das kann ich beantworten: Ich habe einige Zeit darüber nachgedacht, wie ich die Einleitung schreiben kann, ohne auf Begriffe wie Komplexitätsklassen zurückzugreifen. In der aktuellen Fassung benötigt man nur Verweise auf Polynomialzeit und sowas.
• Die Definition sollte einen Informatiker nicht verwirren, denn sie ist eine der gängigen und üblichen Standarddefinitionen. Diejenigen Informatiker, die sie als falsch bezeichnen, lesen halt nicht genau. Vielleicht haben sie sich in den Anfängervorlesungen die Vorstellung in den Kopf gesetzt "NP-vollständig heißt: nicht-det. TM braucht polynomiell lange" und denken aber nicht darüber nach, wofür sie eigentlich polynomiell lange brauchen.
• Die Einleitung hat aber ein anderes Problem: Sie ist immer noch nicht laientauglich. Da denke ich noch drüber nach. ʘχ (Diskussion) 17:15, 26. Sep. 2012 (CEST)

Vielleicht haben sie sich in den Anfängervorlesungen die Vorstellung in den Kopf gesetzt "NP-vollständig heißt: nicht-det. TM braucht polynomiell lange" Möglicherweise hängt das auch damit zusammen, dass man in "nicht-deterministisch polynomielle Zeit zur Lösung" das "N" und das "P" aus der Definition wiederfindet, während in "polynomielle Zeit zur Überprüfung" nur das "P" zu finden ist und das "N" vergeblich gesucht wird - ob solche Merkhilfen immer eine gute Sache sind ist sicher fraglich; andererseits ist in der Einleitung eine Definition, bei der der Bezug zum Namen schwerer erkennbar ist, aber auch nicht optimal. Freundliche Grüße, --Arno Nymus (Diskussion) 22:56, 26. Sep. 2012 (CEST)

"Bezug zum Namen" bei einer solchen Definition? Wie sollte das denn aussehen? In Tat sind diese 'Merkhilfen" nicht zu gebrauchen. Anstatt so eine Art Buchstabensuppe zu haben, wo man Buchstaben drin sucht, sollte man lieber verstehen, worum es geht. ʘχ (Diskussion) 23:33, 26. Sep. 2012 (CEST)

@ʘχ: OK, Du bist also der Meinung, dass es gerade für einen Laien - für den die Einleitung Deiner Meinung ist - nicht hilfreich ist, wenn man in der Kurzdefinition aus der Einleitung einen hilfreichen Bezug zum Namen herstellen kann wie z.B. "Nichtdeterministisch Polynomielle Zeit zur Lösung" für das "NP-" in "NP-vollständig". Gut, das ist Deine Meinung. Wie sehen das die anderen Beteiligten an der Diskussion? Freundliche Grüße, --Arno Nymus (Diskussion) 00:08, 27. Sep. 2012 (CEST)

In der Tat, diese Begriffe und Definitionen sind einfach mathematische Fakten, die man akzeptieren muss. Wenn man nicht weiß, was "nichtdet. Polynomialzeit" ist, es aber wissen will, muss man das nachlesen. Mit Buchstaben umzuhantieren hingegen schafft null Verständnis beim Laien, statt dessen führt das sogar zu falschen Ansichten. ʘχ (Diskussion) 00:17, 27. Sep. 2012 (CEST)

Ich denke, dieses Argument sollte an letzter Stelle stehen. Die Variante über eine polynomielle Überprüfung scheint mir leichter allgemeinverständlich darzustellen. Wenn man mit nichtdeterministischen Rechnern kommt, muss man die erklären, und das ist nicht so einfach, da denkt der unbedarfte Leser dann zunächst „ja wenn die raten können, wo ist dann die Einschränkung? Dann können die doch einfach die richtige Antwort raten?“, da kann ich mir nicht vorstellen, dass in Kürze zu erklären (schließlich geht es in diesem Artikel ja auch um NPC, nicht um nichtdeterministische Turingmaschinen). Aber wenn jemand anders da eine tolle Idee hat… --Chricho ¹ ² ³ 00:17, 27. Sep. 2012 (CEST)

Also das Argument ist vom Prinzip her sehr gut, aber aktuell steht da in der Einleitung

"wenn ein deterministisch arbeitender Rechner nur polynomiell viel Zeit [...]".

Nun wird ein Laie erst mal "deterministisch" ebenso wenig verstehen wie "nicht-deterministisch"; möchte er kurz gucken, was das bedeutet, wird er auf die Turingmaschine weitergeleitet. Absehbar wird ihm das ohne einiges Lesen ebenso nicht viel helfen (Ich kann dabei nur empfehlen, mal zu schauen, wo das erste Mal "deterministisch" im Artikel Turingmaschine vorkommt:

"Formal kann eine deterministische Turingmaschine als 7-Tupel $M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},\square ,q_{f})$ dargestellt werden (siehe auch nichtdeterministische Turingmaschine).").

Entsprechend stimme ich zu, dass der Laie mit dem Begriff "nicht-deterministisch" nicht viel anfangen kann, aber mit dem Begriff "deterministisch" nun mal auch nicht. Selbst wenn man annehmen sollte, dass der Begriff deterministisch leichter zu erklären wäre, muss man ganz klar anmerken, dass diese Erklärung an dieser Stelle schlicht weg korrekterweise nicht erfolgt und nicht verlinkt ist. Hingegen wird der Laie eher noch dadurch verwirrt, dass die für die Initialen verantwortlichen Begriffe ("NP-vollständig (nichtdeterministisch-polynomiell vollständig)") in der Erklärung nicht mehr vorkommen, sondern dann plötzlich auf "deterministisch" gewechselt wird. Für uns, die wir uns mit dem Thema auskennen, mag das verständlich sein, weil wir nun mal die äquivalenten Formulierungen stets parat und leicht zuordnen können - für einen Laien gilt das aber nun mal nicht. Freundliche Grüße, --Arno Nymus (Diskussion) 00:44, 27. Sep. 2012 (CEST)

Äh, dass die Einleitung nicht laientauglich ist, bedarf keines Beweises, denn das ist bekannt, und das habe ich auch oben bereits gesagt. Es ging hier aber gar nicht um die Laien, sondern um die Informatiker, die das nicht verstehen. Das steht auch oben! ʘχ (Diskussion) 00:48, 27. Sep. 2012 (CEST)

Es ist zwar sicher nett gemeint, dass Du schreibst, um welche Personengruppe es Deiner Meinung nach geht, dennoch liegst Du damit falsch in Bezug auf meinen Kommentar. Dieser bezog sich auf Chrichos lesenswerten Einwand zur Allgemeinverständlichkeit und daher natürlich hauptsächlich auf Laien bzw. unbedarfte Leser. Freundliche Grüße, --Arno Nymus (Diskussion) 01:10, 27. Sep. 2012 (CEST)

Und ob das falsch ist! NP-Probleme sind Entscheidungsprobleme, es gibt für diese genau zwei mögliche Lösungen: "Ja" und "Nein". Zum Beispiel: "Ja, es gibt eine Lösung für mein SAT-Problem". Wenn es nun möglich wäre, in P-Zeit zu prüfen, ob "Ja" oder ob "Nein" die korrekte Lösung ist, hätten wir P=NP. --84.46.63.209 09:47, 14. Mai 2013 (CEST)

Hallo natürlich hast du Recht das es sich bei NP-vollständigen Problemen um Entscheidungsprobleme handelt die

mit "Ja" oder "Nein" beantwortet werden. Der Satz in der Einleitung ziehlt aber darauf ab das es für jedes

NP-Problem und jede Instanz die mit 'Ja' beantwortet werden kann einen "Beweis" (oder eben eine Lösung) gibt

der in Polynomialzeitverifiziert werden kann. Da es sich bei der Einleitung ja nicht um eine formale Definition

sondern um eine Beshreibung für den "Laien" handelt, und die Beschreibung die Intuition von NP-vollständigen

Problemen recht gut trifft, passt der Satz meiner Meinung nach ganz gut -- lg Wdvorak (Diskussion) 20:45, 14. Mai 2013 (CEST)

Danke, Wdvorak, für deine verständnisvollen Worte. Um der Präzision willen habe ich nun darüber nachgedacht, die Einleitung um den Hinweis zu ergänzen, dass sie sich auf das mit dem Entscheidungsproblem assoziierte Suchproblem bezieht. ʘχ (Diskussion) 22:48, 14. Mai 2013 (CEST)

Fehler

Die Komplexitätsklasse NP beschreibt alle Sprachen/Probleme, welche sich auf einem NICHTdeterministischen Rechner in Polynomialzeit entscheiden lassen.

--77.2.222.42 23:49, 9. Dez. 2012 (CET)

Siehe einen Abschnitt darüber, es stimmt schon so. --Chricho ¹ ² ³ 00:44, 10. Dez. 2012 (CET)

Es ist aber sehr verwirrlich, auch für nicht-laien. Auf jeden Fall nicht die Definition, welche man erwarten würde. --84.75.130.30 19:39, 14. Dez. 2012 (CET)

Es ist meines Erachtens die intuitivere, leichter fassbare und in ihrer Bedeutung schneller klarere Definition. --Chricho ¹ ² ³ 20:01, 14. Dez. 2012 (CET)

Mit dieser Meinung dürftest Du ziemlich allein sein. Der fehlende Verweis auf nichtdeterministisch hat mich erst einmal zweifeln lassen, und das Gefasel über vorgeschlagene Lösung (was ist das, von wem vorgeschlagen?) verwirrt völlig. Man sollte eine Definition so angeben, wie sie üblich ist, äquivalente Formulierungen kann man später immer noch angeben (wie das jedes Mathe-Buch macht, da heißt sowas dann Satz oder Theorem oder so ähnlich). Auf eine Änderung verzichte ich, macht sowieso nur Ärger. --132.195.106.57 19:23, 27. Mär. 2013 (CET)

Schwach und stark NP-vollständig

Haben diese Begriffe irgendeine mathematisch/informatische Bedeutung, außer für die informelle Kommunikation? Welche dieser Attribute ein Problem erhält, hängt letztlich nur davon ab, was man unter einem numerischen Parameter versteht. Wenn man durch geeignete Kodierung alle Parameter als numerisch auffasst, sind alle NP-vollständigen (es ließe sich weiter treiben mit EXPTIME) Probleme nur schwach NP-vollständig. Und macht eine informelle Bewandnis der Bezeichnungen das relevant für diesen Artikel? Man könnte auch ohne diese Begriffe erwähnen, dass mitunter für die Praxis relevante pseudopolynomielle Algorithmen für NP-vollständige Probleme existieren. --Chricho ¹ ² ³ 01:08, 10. Dez. 2012 (CET)

In der Praxis auftretende Größenordnungen

Der Satz "In der Praxis wirkt sich diese Eigenschaft nicht in jedem Fall negativ aus, das heißt, es gibt für viele NP-vollständige Probleme Lösungsverfahren, anhand derer sie für in der Praxis auftretende Größenordnungen in akzeptabler Zeit lösbar sind." im Einleitungsteil ist imho nicht korrekt. Richtig wäre meiner Meinung nach, dass es für viele Probleme Annäherungen an die optimale Lösung gibt, die in Polynomialzeit mit konfigurierbarer Genauigkeit arbeiten. In der englischen Wikipedia steht dazu auch "NP-complete problems are often addressed by using approximation algorithms." --empi (Diskussion) 18:56, 20. Mär. 2013 (CET)

Das sind doch zwei völlig voneinander unabhängige Aussagen. Wo siehst du den Widerspruch? --Chricho ¹ ² ³ 19:00, 20. Mär. 2013 (CET)

Naja, wenn ich nicht gerade total auf dem Schlauch stehe behauptet der Artikel das NP-Vollständige Probleme so wie sie sind in akzeptabler Zeit korrekt lösbar sind. Soweit ich weiß wird aber in der Praxis das Ergebnis nur angenähert, so lese ich das auch in der englischen Wikipedia. --empi (Diskussion) 19:08, 20. Mär. 2013 (CET)

Na, es gibt beides. Mal werden Approximationen benutzt, mal auch nur Heuristiken, von denen nicht bewiesen ist, dass sie einen gewissen Grad der Approximation erreichen, und mal sind die Probleminstanzen tatsächlich so klein, dass eine perfekte Lösung in annehmbarer Zeit möglich ist. Ein dritter Aspekt spielt noch hinein, dass man es in der Praxis oft nur mit gewissen speziell gearteten Probleminstanzen zu tun hat. So werden in der Praxis durchaus etwa SAT-Instanzen in Millionengröße gelöst, während andere, konstruierte und viel kleinere Instanzen die Algorithmen in die Knie zwingen können. --Chricho ¹ ² ³ 20:13, 20. Mär. 2013 (CET)

definition

ich halte es nicht fuer sinnvoll, die zugehoerigkeit eines entscheidungsproblems zu NP ueber das zugehoerige suchproblem zu definieren. das ist zwat eine korrekte charakterisierung, aber als primaerdefinition halte ich das fuer verwirrend. besser finde ich die definition, dass zu jeder loesung ein zeuge existiert, der es erlaubt, in polyzeit die korrektheit der loesung zu verifizieren. damit faellt der umstaendliche verweis auf das zugehoerige suchproblem weg. --Mario d 11:22, 17. Mai 2013 (CEST)

Die ursprüngliche Motivation war, eine Formulierung zu finden, die maximal laientauglich ist. Aufgrund der Problematik mit Entscheidungs- und Suchproblemen etc. ist daraus aber leider nicht so richtig was geworden. Mittlerweile habe ich den Eindruck, dass es sein könnte, dass man NP-Vollst. gar nicht laientauglich erklären kann, oder zumindest nicht, ohne sehr weit auszuholen (WP-unüblich). Das Verifizieren von Beweisen halte ich auch für eine Möglichkeit. Man muss nur irgendwie verständlich rüberbringen, was ein solcher Beweis ist, denn das bloße Verweisen auf andere Artikel wird dem unkundigen Leser wenig nützen. ʘχ (Diskussion) 17:33, 17. Mai 2013 (CEST)

Das zugehörige Suchproblem ist ja nichts anderes als dieser Zeuge. Ich habe dasselbe Problem wie mein Vorredner, dass ich nicht weiß, wie man das rüberbringt, was dieser Zeuge (bzw. das zugehörige Suchproblem) ist. --Chricho ¹ ² ³ 17:37, 17. Mai 2013 (CEST)

das eigentliche problem hier ist ja die definition von NP. NP-C kann recht einfach als die klasse der schwersten probleme in NP erklaert werden. bei NP steht in der einleitung "Intuitiv beschrieben, enthält NP die Entscheidungsprobleme, bei denen es für „Ja“-Antworten Beweise gibt, die effizient (in Polynomialzeit) verifiziert werden können." - das finde ich ziemlich gut erklaert, was ein beweis ist, ist ja intuitiv klar. --Mario d 22:23, 17. Mai 2013 (CEST)

Gerade die Formulierung der "schwersten Probleme in NP" halte ich für ungünstig, weil sie nur dem Fachmann etwas sagt. Dem Laien muss erst erklärt werden, was NP ist und was "schwerer sein" bedeutet. Die Erklärung ist zwar kurz, aber kurz heißt ja nicht gut oder verständlich, erst recht nicht, wenn man die Kürze durch Auslassung erkauft. Ich finde, man muss die Erklärung für den Laien nochmal ganz überdenken. ʘχ (Diskussion) 22:36, 17. Mai 2013 (CEST)

ich finde, dass es ziemlich intuitiv ist, dass manche probleme schwerer sind als andere. was das genau bedeutet, ist ja fuer das grobe verstaendnis unerheblich, es geht ja nur um eine grobe erste naeherung fuer laien. --Mario d 14:10, 21. Mai 2013 (CEST)

Ich denke man muss sich in (dem ersten Teil) der Einleitung von der formalen Definition lösen. Für in NP gefällt mir die Charaktersisierung mittels effizient verifizierbarer Beweise recht gut - die dazu passende Erklärung für NP-Schwere wäre dass man diesen Beweis nicht effizient berechnen kann (wegen des großen Suchraums). Da man vage Begriffe wie Beweis/Lösung immer leicht falsch/unterschiedlich interpretieren kann wäre aber glaube ich ein Beispiel sehr hilfreich. Ich habe unten mal ein Vorschlag gepostet wie ich mir das vorstellen würde -- Wdvorak (Diskussion) 20:33, 21. Mai 2013 (CEST)

Vorschlag

In der Informatik bezeichnet man ein Problem als NP-vollständig (vollständig für die Klasse der Probleme, die sich nichtdeterministisch in Polynomialzeit lösen lassen), wenn es sowohl in er Klasse NP liegt, als auch NP-schwer ist. Intuitiv beschrieben sind das die Entscheidungsprobleme bei denen es für „Ja“-Antworten Beweise gibt die effizient (in Polynomialzeit) verifiziert werden können, aber diese Beweise aufgrund des exponentiell großen Suchraums nicht effizient berechnet werden können. Ein Beispiel für ein solches Problem ist zu Entscheiden ob ein Sudoku eine gültige Lösung hat. Hat man eine Lösung kann man diese effizient verifizieren und mit "Ja" antworten. Der Suchraum der poteniellen Lösungen ist aber exponentiell in der Größe des Sudokus und daher kann das finden einer Lösung aufwändig sein.

Danke sehr für den Vorschlag. Dass der erste Satz Bezug auf NP nimmt, lässt sich vielleicht nicht mehr vermeiden (ich fürchte es). Allerdings habe ich etwas Schwierigkeiten mit diesem Satzteil:

[...], aber diese Beweise aufgrund des exponentiell großen Suchraums nicht effizient berechnet werden können.

Das impliziert einerseits P!=NP und andererseits auch noch eine Art von "Grund" dafür (exponentieller Suchraum), der aber nicht bekannt ist.

Zum nachfolgenden Beispiel: Beispiele halte ich natürlich generell für sinnvoll, allerdings nicht in der Einleitung (und sogar wenn, dann nicht gleich im ersten Absatz). Einerseits halte ich das stilistisch für nicht gut, und andererseits ist es ein Zeichen, dass der Text entweder unverständlich oder unvollständig ist (oder auch beides). ʘχ (Diskussion) 22:42, 21. Mai 2013 (CEST)

1) Ja das sollte natürlich ein vermutlich nicht effizient berechnet sein. Der exponentielle Suchraum ist meiner Meinug nach eine sehr charakteristische Eigenschaft (notwendig aber natürlich nicht hinreichend) von NP-schweren Problemen. Dieser Satzteil hat aber definitiv noch Verbesserungspotential.

2) Gerade in Einleitungen bei der man einerseits nicht alle Begriffe rigoros einführen kann (und damit zwangsläufig unvollständig ist) und anderseits auch davon ausgehen muss dass der/die Leser(in) auch nicht mit diesen vertraut ist, sind meiner Meinung nach Beispiele ein probates Mittel um die Intuition einer Aussage zu vermitteln. Das soll/kann aber natürlich kein Ersatz für präzise Erklärungen sein, welche aber meistens für Fachfremde nur schwer zugänglich sind -- Wdvorak (Diskussion) 13:26, 31. Mai 2013 (CEST)

Polynomialzeitreduktion uneindeutig

Im Artikel wird NP-Vollständigkeit über Polynomialzeitreduktionen definiert. Der Artikel zu diesem Thema beschäftigt sich allerdings mit verschiedenen Arten von Reduktionen, von denen nur eine zur Definition für NP-Vollständigkeit korrekt ist:

Polynomiell beschränkte Turingreduktionen werden (nach Stephen A. Cook) auch als Cook-Reduktion 
bezeichnet. Meist bezieht sich der Begriff Polynomialzeitreduktion jedoch auf eine polynomiell 
beschränkte many-one-Reduktion (auch Karp-Reduktion, nach Richard M. Karp). 

Der Artikel zu NP-Vollständigkeit sollte klarstellen, welche Art von Reduktion gemeint ist (polynomielle many-one-reduction). Die Verwendung der Relation $\preceq _{p}$ ist aus gleichem Grunde problematisch, da diese Relation in Wikipedia nicht klar definiert wird (es wird nirgends geklärt, ob sie sich auf many-one- oder Turing-Reduktionen bezieht).

Allgemein sollte man darüber nachdenken, ob es wirklich sinnvoll ist, Reduktionsfunktionen nach ihrer Zeitkomplexität zu gruppieren ("Polynomialzeitreduktion"), anstatt nach Art der Funktion. Es scheint zweitrangig ob zwei so unterschiedliche Dinge wie many-one- und Turing-Reduktion die gleiche Zeitkomplexität haben. Ich kenne zumindest keinen Zusammenhang, indem man sinnvollerweise von einer Polynomialzeitreduktion sprechen kann, ohne auch deren genauen Typ zu nennen. --Markus Krötzsch (Diskussion) 18:59, 15. Feb. 2015 (CET)