Diskussion:Komplexitätstheorie

Dieser Artikel war am 26. April 2007 der Artikel des Tages.

Entfernter Abschnitt

Ex-Inhalt Verschoben nach Komplexitätsklassen

---

Ich hab' folgenden Abschnitt wieder erntfenrt, weil er in dieser Form nicht so recht in den Artikel pass. ICh kann nicht beurteilen, ob es sachlich richtig ist. Falls ja wäre es toll wenn ihn jemand in geeigneter Weise einbauen würde. Also, hier ist er:

Es gilt darauf hinzuweisen, dass die Komplexitätstheorie mit dem reinen Informatikbezug nicht ausreichend dargestellt ist. Da sehr viele komplexe System, z.B. das Verhältnis und Verhalten von "Reiter und Pferd", mathematisch nicht oder höchstens näherungsweise zu beschreiben sind, benötigt eine umfassende Darstellung der Systemtheorie komplexer Systeme die Ergänzung durch Grenzflächenbeschreibungen, die sich mit Phänomenen der Emergenz, Phasenübergänge und Non-Linearität beschäftigen. Ergänzungstheorien hierzu sind in dem Bereich der Immersion, des ZEN und der Synchronisation zu finden.

-- D. Düsentrieb ⇌ 13:33, 12. Nov 2004 (CET)

Das paßt so. Obiger Abschnitt hat ganz und gar nix mit der im Artikel behandelten Komplexitätstheorie als Teilgebiet der Theoretischen Informatik zu tun (mit welcher Komplexität sonstwo will ich nicht beurteilen). --Bri B. 11:01, 15. Feb. 2010 (CET)

Ex-Inhalt Verschoben nach Komplexitätsklassen

---

Ausarbeitung dieses Artikels

Hallo, wer diesen Artikel oder die Kategorie in Beobachtung hat, mag bemerkt haben, dass ich derzeit eine Ausarbeitung des Artikels vornehme. Hierzu eine Anmerkung. Ich bin mir der Tatsache bewusst, dass ich die Thematik stellenweise recht umfangreich in ihren Bezügen zu verwandten Begriffen (z.B. Problem, Maschinenmodell usw.) bearbeite. Wer es kurz und knapp liebt, wird dies zunächst etwas langatmig finden. Ich werde daher zum Abschluss meiner Arbeiten an dem Artikel auch versuchen, die Abschnitte insgesamt zu verkürzen und auf das Wesentliche zu reduzieren. Sollte mir dies nicht als sinnvoll erscheinen, so werde ich die dann erreichte Version in ein Wikibook umwandeln und durch eine komprimierte Version in der Wikipedia ersetzen, mit der alle Seiten leben können. Vorläufig möchte ich jedoch darum bitten, nicht größere Abschnitte wegen Weitschweifigkeit zu entfernen. Vertraut mir einfach mal, dass ich hier an einer guten, durchaus griffigen Darstellung der Komplexitätstheorie interessiert bin und mich hier nicht unnötig kaprizieren will. Ich halte den Artikel für das Herz eines recht großen Teilbereichs der theoretischen Informatik und möchte daher eine angemessene und verständliche Darstellung der Thematik erreichen. Ich setze dabei nicht jeden Fachbegriff voraus, um ein einheitliches Lesen und Verstehen zu ermöglichen. Die Komplexitätstheorie ist erfahrungsgemäß ein bei Studenten und Lernenden unbeliebtes Gebiet der Informatik. Dies liegt nach meiner Ansicht zum großen Teil daran, dass sich die bekannten Darstellungen in formalen Details verlieren und die größeren Zusammenhänge vernachlässigen. Es ist mir daher daran gelegen, diese Zusammenhänge zu verdeutlichen, ohne allzu sehr in die formalen Inhalte einzusteigen (dies wäre tatsächlich eher eine Idee für ein Wikibook). Da ich dies nicht an einem Tag leisten kann, lasse ich den Artikel nun zunächst anwachsen, um ggf. später überflüssige Teile wieder rauszuwerfen. Ich hoffe, mit dieser Arbeitsweise könnt ihr für eine Weile leben. Inhaltliche wie auch sprachliche Korrekturen sowie insbesondere eine intensivere Verlinkung sind natürlich immer willkommen. Gerne stehe ich auch für inhaltliche Diskussionen zur Verfügung. Viele Grüße --Mkleine 03:41, 17. Jan 2005 (CET)

Ähmm... Wie? Was? Kürzen? Wo muss man jetzt kürzen. Es ist imho noch viel zu knapp dargestellt. Übrigens vielen Dank für die Ausarbeitung. Der Artikel ist schon deutlich besser als früher und du machst kaum inhaltliche Fehler. In ganz seltenen Fällen muss man noch auf POV achten. Was du bei den letzten Bearbeitungen leider unter den Tisch fallen lassen hast, sind die randomisierten Algorithmen bzw. Rechnermodelle, die ich durchaus für einen sehr wichtigen Teil halte und die auch wichtige Komplexitätsklassen bilden, die man hier darstellen oder wenigstens erwähnen sollte. Die Quantencomputermodelle sind tatsächlich weniger wichtig (es gibt imho bisher nur 3 eng verwandte Problem, die sie im Vergleich zu herkömmlichen Maschinen effizient lösen können oder könnten, wenn es sie schon gäbe) und viel könnte ich mangels Kenntnis auch nicht dazu zu sagen. Allerdings sind sie (bzw. sollen sie es sein) ein gutes Beispiel, wo auch eine andere Ressource als Zeit oder Platz eine Rolle spielt. Erwähnt werden sollte vielleicht, das Platzkomplexität nur selten betrachtet wird und in der Praxis kaum relevant ist, da großer Platzbedarf sowieso meist auch großen Zeitbedarf impliziert bzw. umgekehrt geringer Zeitbedarf geringen Platzbedarf impliziert. Ansonsten werde ich weiter kritisch über deine Schulter schauen. Aber viel zu beanstanden werde ich wohl nicht haben. Weiter so! --Coma 04:48, 17. Jan 2005 (CET)

Hallo, danke für die Ermutigung. Bzgl. der randomisierten Rechnermodelle ist mir keine durch sie definierte Komplexitätsklasse bekannt - hat diese einen etablierten Namen? Trotzdem ich knapp ein halbes Dutzend relativ bekannte Werke zur theoretischen Informatik zu Rate ziehe (Asteroth/Baier, Erk/Priese, Socher, Schöning, Wiener), konnte ich hierzu nichts Näheres finden und habe das Modell daher vorläufig aus dem Artikel entfernt. Auch randomisierter Algorithmus geht nicht auf Komplexitätsklassen ein. Wenn du mir eine solche nennen kannst, würde ich mich in dieser Richtung mal schlau machen und das Maschinenmodell wieder aufnehmen.

Im Prinzip sind randomisierte Rechnermodelle nur durch die Möglichkeit erweitert, Münzen werfen zu können und je nach Ausgang des Wurfs in die eine oder andere Richtung weiterzuarbeiten. Letztlich ist das vom Rechnermodell äquivalent zu nicht-deterministischen Maschinen, allerdings wird die Berechnung anders interpretiert. Dafür gibt es im wesentlichen zwei Modelle. Zum einen Monte-Carlo-Algorithmen, bei denen das Ergebnis nur mit kleiner Wahrscheinlichkeit falsch ist (man verlangt meist nur, dass die Fehlerwarscheinlichkeit unter 1/2 liegt. Durch mehrfache Anwendung lässt sich diese dann sehr schnell so klein machen, dass die Wahrscheinlichkeit unter die der Fehlerwahrscheinlichkeit von Hardware fällt ohne die Komplexitätsklasse zu verlassen [es erhöht sich nur der Vorfaktor in der O-Notation]) und Las-Vegas-Algorithmen, die immer exakte Ergebnisse liefern, dafür aber mit geringer Fehlerwarscheinlichkeit länger für die Berechnung brauchen, als die Komplexitätsklasse benötigt. Beide Varianten sind somit ähnlich zu nichtdeterministischen Algorithmen. Letztere verlangen ja nur die Existenz eines Rechenweges, der zum exakten Ergebnis unter vorgeschriebener Zeit führt. Randomisierte Algorithmen verlangen dies für die Mehrheit der Rechenwege. Die Komplexitätsklassen werden in der Regel genauso bezeichnet, wie ihre deterministischen Varianten mit vorangestelltem R, welches für Random steht. RP ist also die Menge aller Probleme, die sich mit randomisierten Algorithmen in (erwartet) polynomieller Zeit lösen lassen.

Ansonsten ist in dem Zusammenhang "deterministisch, randomisiert, nichtdeterministisch) auch noch das PCP-Theorem (haben wir leider noch keinen Artikel zu, wäre aber auch nur was für Informatiker, ist nämlich nicht ganz trivial, einfach mal danach googeln!), welches eine schöne neue Charakterisierung der Klasse der NP liefert. Das Theorem selbst lässt sich noch relativ leicht mit den richtigen Maschinenmodellen erklären. Der Beweis ist hingegen (noch) ziemlich kompliziert und lang. --Coma 14:49, 17. Jan 2005 (CET)

Danke für die Hinweise. Einige Artikel zu Komplexitätsklassen auf der Basis randomisierter Rechnermodelle habe ich indessen auch in der englischen wp gefunden. Ich werde das an geeigneter Stelle in den Artikel aufnehmen. --Mkleine 16:50, 17. Jan 2005 (CET)

An randomisierten Komplexitätsklassen könnte ich Dir RP und BPP anbieten. Ein paar Komplexitätstheoretiker lieben die (siehe z.B. Ingo Wegener, "Komplexitätstheorie", Springer), die anderen vernachlässigen sie oft ziemlich. Aber der Vollständigkeit halber sollten sie schon erwähnt werden, denke ich. Wenn Du nichts dazu findest, kann ich sonst auch ein bisschen was schreiben (muss mich aber auch erst wieder einlesen). --Pinguin.tk 17:58, 17. Jan 2005 (CET)

Was die Platzkomplexität betrifft, so ergibt sich natürlich schon aus den - noch zu behandelnden - Hieararchiesätzen ein enger Zusammenhang mit der Zeitkomplexität. Es gibt daher einige wichtige Zusammenhänge mit einzelnen Komplexitätsklassen, so sind z.B. die Probleme aus NC gerade diejenigen, die sich mit logarithmischem Platz berechen lassen. Logarithmische Bandreduzierbarkeit kann daher schon ein wichtiges Beweismittel sein, aber freilich kann man da auch nicht allzu tief einsteigen. Dennoch gibt es in der Tat insgesamt noch ein weites Feld zu beackern. Da zusammenfassende Texte jedoch bislang Mangelware sind, könnte es durchaus sein, dass ich hier und da etwas über das Ziel hinaus schieße, und ich wollte darum schonmal vorbeugen. In der Regel bemerke ich es später selbst, wenn meine Erläuterung zu weit ausufert und korrigiere dies dann. Viele Grüße --Mkleine 13:50, 17. Jan 2005 (CET)

---

Von den Bedingungen:

1. f(n+1) ≥ f(n) (monotones Wachstum).
2. Die Funktion f muss selbst in Zeit O(f) und mit Raum O(f) berechenbar sein.

an die Schrankenfunktionen habe ich noch nie was gehört. Die Erste scheint sinnvoll aber nicht notwendig. Den Sinn der Zweiten sehe ich überhauptnicht zumal ich sie auch nicht glaube. Schon Multiplikation und Division sind quadratisch. --Coma 06:43, 2. Feb 2005 (CET)

Die Bedingungen gelten für "echte Komplexitätsfunktionen". Verwendet man andere Schrankenfunktionen (was ja durchaus erlaubt ist), so können sehr unerwartete Ergebnisse hergeleitet werden. Multiplikation und Division fallen ohnehin aus der O-Notation als lineare Faktoren raus. Für die anderen Funktion lässt sich die Behauptung ebenfalls (wenn auch nicht trivial) beweisen. Letztlich setzt man die Einschränkungen aus technischen Gründen, aber mir war wichtig zu erwähnen, dass die Wahl der Schrankenfunktion nicht beliebig ist. Man stelle sich etwa eine Maschine vor, deren Zeitfunktion mit wachsender Eingabe so sinkt, dass sie nichteinmal mehr genügend Schritte ausführt, um die Eingabe zu lesen. Eine Maschine, die nichteinmal ihre Eingabe mehr vollständig liest, dürfte kaum eine sinnvolle Funktion berechnen. Derartige "pathologische" Fälle lassen sich über die genannten Einschränkungen ausschließen. --Mkleine 13:22, 2. Feb 2005 (CET)

Zu den einflussnehmenden Faktoren:

1. Das zugrundeliegende Berechnungsmodell (Turingmaschine, Registermaschine usw.).
2. Das angenommene Kostenmaß (uniform, logarithmisch).

Ich glaube Registermaschinen sind genau für uniforme und Turingmaschine für logarithmische Kostenmaße gedacht. --Coma 06:43, 2. Feb 2005 (CET)

Das klingt plausibel, wobei ich mir vorstellen könnte, dass man das Registermaschinenmodell auch auf Binärzahlen arbeiten lassen könnte, um damit ein logarithmisches Kostenmaß zu gewinnen. Grüße --Mkleine 13:22, 2. Feb 2005 (CET)

---

Meine Ausarbeitung habe ich vorläufig abgeschlossen. Gelegentlich werde ich hier sicher noch Kleinigkeiten hinzufügen. Fertig ist der Artikel (leider) noch lange nicht. Aber immerhin steht jetzt ein wenig mehr drin als zu Beginn. Ich bin guter Hoffnung, dass weitere Autoren hier jetzt eine vernünftige Basis und Struktur vorfinden, um weitere Ergebnisse der Komplexitätstheorie bei Bedarf relativ schnell einarbeiten zu können. Leerüberschriften habe ich nun entfernt, um ein einheitliches Lesebild zu erreichen. Viele Grüße --Mkleine 23:30, 27. Feb 2005 (CET)

Ich ergänze nochmal meine Liste von Themen, die ich hier eigentlich noch einbauen wollte. Vielleicht kommt ja jemand dazu:

• Erweiterte Church'sche These: alle universellen Maschinen leisten dasselbe.
• P/NP-Problem als treibende Fragestellung.
• Hierarchie der Komplexitätsklassen als zentrales Ergebnis der Komplexitätstheorie
• grobe Darstellung der Geschichte und Nennung der wichtigsten Forscher
• Einordnung in die theoretische Informatik insgesamt --Mkleine 01:31, 28. Feb 2005 (CET)

Themenbereich Veränderung der Komplexität durch Problemdarstellung

Es fehlt meiner Meinung nach noch ein wichtiges Thema der Komplexitättheorie. Die Veränderung der Kosten durch den Einsatz verschiedener Problemdarstellungen, bzw. die "Widerspenstigkeit" einiger Probleme gegen über mächtigeren Darstellungsarten (z.b Nicht-Determinismus). Insbesondere als Bereich der Beschreibungskomplexität - Repräsentation einer Sprache in verschiendenen Grammatiken und mögliche Einsparungen in der Größe der Grammatik abhängig vom Typ --Peter Biela 14:48, 26. Apr. 2007 (CEST)

Die wichtigsten Schrankenfunktionen

Heißt das "polynomiell" oder nicht eher "polynomial"? --NeoUrfahraner 17:32, 9. Mär 2005 (CET)

Wohl eher letzteres. Ich habs's mal geändert. --Mkleine 18:50, 9. Mär 2005 (CET)

Wir verwenden an der Uni eigentlich immer "polynomiell" - die "-ial"-Form kommt wohl aus dem Englischen.

Existenz von Einwegfunktionen

Vielleicht versteh ich den Satz ja völlig falsch, aber im Abschnitt Geschichte unter Randomisierte Komplexitätsklassen steht:

"1984 weisen schließlich Oded Goldreich, Shafi Goldwasser und Silvio Micali die Existenz von Einwegfunktionen (one way functions) nach, die eine Verallgemeinerung der Falltürfunktionen darstellen und randomisierten Komplexitätsklassen zu Grunde liegen."

Meines Wissens ist die Existenz von Einwegfunktionen keineswegs bewiesen, sondern ein noch sehr interessantes aber auch sehr offenes Problem, dessen Antwort weitreichende Konsequenzen hat (siehe auch das entsprechende Lemma dazu). Könnte mich bitte jemand aufklären, auf welche Publikation von Goldreich, Goldwasser und Micali angespielt wird, bzw. wie der zitierte Satz zu verstehen ist, oder ggf. den Abschnitt richtig stellen? Danke. --MRA 17:41, 25. Jul 2005 (CEST)

Kann ich mir auch nicht vorstellen, weil damit imho auch P!=NP folgen würde. --Coma 18:44, 25. Jul 2005 (CEST)

Da scheinbar niemand gegenteiliges zu Tage bringt und Goldwasser und Bellare diesem selbst widersprechen ("Although one-way functions are widely believed to exist, [...] we currently do not know how to mathematically prove that they actually exist", siehe [1], Seite 12f.), werde ich den Abschnitt korrigieren. -- MRA 17:41, 3. Aug 2005 (CEST)

Lesenswert-Diskussion

Scheint alles drin zu sein, was rein gehört. Kaum Fehler gefunden. Manchmal etwas unklar ausgedrückt. Aber sicher Lesenswert!

 Pro --Koethnig 16:21, 28. Dez 2005 (CET)

Vielleicht mache ich aufgrund der Uhrzeit einen Denkfehler, aber ist im Abschnitt Zeithierarchiesatz die Inklusion :$DTIME(f(n))\subset DTIME(f(n)\cdot log^{2}(f(n)))$ nicht gerade falsch herum? So herum ist sie doch trivial (mehr Zeit reicht erst recht), oder nicht? --Christian Gawron 00:55, 29. Dez 2005 (CET)

Also wenn ich den Text dazu richtig verstanden habe, soll die Beziehung nicht den trivialen Sachverhalt ausdrücken, dass die linke Seite in der rechten enthalten ist, sondern in der rechten Seite Dinge enthalten sind, die nicht in der linken Seite enthalten sind, es sich somit um eine echte Inklusion handelt, die dann natürlich nicht mehr trivial ist. --Koethnig 01:22, 29. Dez 2005 (CET)

Dafür gibt es evtl. ein extra Symbol in LaTeX - ich schaue das nach und ändere dann ggf. den Text. Jedenfalls schließt nach gänger Mengentheorie die Inklusion Gleichheit nicht aus. --Christian Gawron 14:28, 30. Dez 2005 (CET)

Ähm, es gibt im Wesentlichen 3 Symbole. Das verwendete, welches meist mit der Bedeutung Inklusion ohne Gleichheit verwendet wird, manchmal aber auch mit ihr. Größere Klarheit bringen noch die Symbole mit Strich drunter (enthält Gleichheit) und durchgestrichenem Strich drunter (enthält Gleicheit nicht). --Koethnig 17:55, 30. Dez 2005 (CET)

• vorsichtiges  Pro. Bin nicht ganz vom Fach, aus meiner Sicht wirkt er aber solide und fundiert. Außerdem angenehm illustriert norro 18:08, 30. Dez 2005 (CET)

•  Neutral: Ich habe den Artikel nur teilweise überflogen. Er scheint soweit recht gut zu sein, aber Literaturhinweise fehlen noch völlig. Selbst wenn es zu umfangreich wäre, die gesamte Originalliteratur aufzulisten, wäre es vielleicht doch angemessen, einige aktuelle Standardwerke dazu zu nennen. --AFBorchert 13:08, 31. Dez 2005 (CET)

•  Pro: Es sollten aber noch einige Interwiki-Links eingefügt werden. --Fredstober 19:58, 1. Jan 2006 (CET)

Pandora-Vermutung -Alle Bilder der Welt

Ich hoffe, ich bin hier richtig. Klingt ja alles mächtig kompliziert für Laien. Kennt jemand die Pandora-Vermutung (Alle Bilder der Welt). Siehe Diskussion:Würfel_im_Rollenspiel#37_Seitiger_W.C3.BCrfel_.2FVorstufe_zum_100-Seitigen --Kungfuman 19:43, 28. Feb 2006 (CET)

Verständlich?

Ich zitiere aus dem Abschnitt Hierarchiesätze:

Exkurs: Derartige Probleme gibt es beispielsweise im Bereich der probabilistischen Komplexitätsklassen. Schränkt man hier - wie für praktisch verwendbare probabilistische Algorithmen erforderlich - die Fehlerwahrscheinlichkeit ein, so resultiert daraus u.a., dass die Komplexitätsklassen nicht mehr aufzählbar sind. Dies ist aber für alle Separationsverfahren eine Voraussetzung. Als Ergebnis lassen sich Polynomzeitalgorithmen plötzlich durch Linearzeitalgorithmen ersetzen. Das Beispiel zeigt, wie sensibel das Geflecht aus Voraussetzungen und den abgeleiteten Sätzen insgesamt ist.

Versteht jemand, was dieser Text sagen will? --MRA 02:48, 3. Aug 2006 (CEST)

Beschränkung auf Entscheidungsprobleme

Man könnte annehmen, dass die Einschränkung auf solche Entscheidungsfragen viele wichtige Probleme ausschließt. Das ist jedoch nicht so. So lassen sich alle relevanten Probleme auch als Entscheidungsproblem formulieren. Betrachtet man z.B. das Problem der Multiplikation zweier Zahlen, so besteht die dazugehörige Sprache des Entscheidungsproblems aus allen Zahlen-Tripeln (a,b,c) für die der Zusammenhang a \cdot b = c gilt. Die Entscheidung, ob ein gegebenes Tripel zu dieser Sprache gehört, entspricht dem Lösen des Problems der Multiplikation zweier Zahlen.

Dieses Beispiel leuchtet mir nicht ein: Es skizziert zwar den Nachweis, daß die Berechnung einer Abbildung (hier der Multiplikationsabbildung) aus der Berechnung der zugrundeliegenden Relation rekonstruiert werden kann. Diese Rekonstruktion ist aber sehr aufwendig - die naive Rekonstruktion dauert im Beispiel länger als die ursprüngliche Multiplikation. Da es in diesem Artikel gerade um die Komplexität von Algorithmen geht, verstehe ich nicht, inwiefern das weiterhilft. --FRR 15:24, 4. Aug 2006 (CEST)

Das Beispiel dient doch nur zur Veranschaulichung. Natürlich würde niemand auf Sprachtheorien zurückgreifen, um zwei Zahlen zu multiplizieren. Für die Klassifikation ist es sinnvoll, Probleme auf andere Komplexitätsklassen bzw. Darstellungsweisen zu reduzieren. --Bri B. 11:41, 15. Feb. 2010 (CET)

Menge der inhärent schwierigen Probleme

An die Autoren: Könnt man die Menge der inhärent schwierigen Probleme in der Einleitung genau/genauer definieren ? Gruß Boris Fernbacher 09:27, 24. Okt. 2006 (CEST)

logarithmisches Kostenmaß

Der folgende Satz ist Unsinn: Der Bezug auf den Logarithmus ergibt sich daraus, dass sich eine n-stellige Dezimalzahl durch log(n) Binärziffern darstellen lässt.

Vermutlich ist gemeint, dass sich die Zahl n mit log(n) (Binär)Ziffern darstellen lässt. Mit der Dezimaldarstellung hat das aber gar nichts zu tun. Bin mir nicht ganz sicher, was mit dem Satz ausgesagt werden sollte, deswegen frage ich mal nach, bevor ich was ändere. 129.143.13.82 21:58, 27. Okt. 2006 (CEST)

Lustig, genau dasselbe wollte ich auch erfragen. Ich ändere das mal entsprechend (und zwar in den Logarithmus zur Basis 2). --Scherben 22:17, 6. Nov. 2006 (CET)

Exzellenzkandidatur Oktober/November 2006

Diese Kandidatur läuft vom 24. Oktober bis zum 13. November 2006.

Die Komplexitätstheorie als Teilgebiet der Theoretischen Informatik befasst sich mit der Komplexität von algorithmisch behandelbaren Problemen auf verschiedenen mathematisch definierten formalen Rechnermodellen. Die Untersuchung der Komplexität bezieht sich dabei auf die Ressourcen, die zur Lösung eines Problems benötigt werden.

• pro: Der Artikel ist vor knapp einem Jahr ohne Gegenstimme lesenswert gewählt worden und ich sehe keinen Grund warum er nicht exzellent werden sollte. Ich persönlich bin nicht vom Fach, finde den Artikel aber gut verständlich und umfangreich (sogar einige nette Grafiken sind drin ;) Der Artikel hat mir einen guten Einblick in ein recht komplexes Thema verschafft. --201.21.236.21 00:15, 24. Okt. 2006 (CEST)

• pro: Als Halblaie auf dem Gebiet habe ich fast alles verstanden. Die Struktur ist hervorragend, und der Text enthält viele (mehr oder weniger laienverständliche) Beispiele, womit er sich deutlich von vielen anderen komplexitätstheoretischen Artikeln abhebt. Ein paar Kleinigkeiten: Bei der erweiterten Church-Turing-These fehlt mir ein Satz zum Status dieser These. Wird allgemein vermutet, dass sie stimmt, oder eher nicht? In der Einleitung der Church-Turing-These steht, dass sie wegen inhärenter Schwammigkeit unbeweisbar ist, wenn ich das richtig verstehe. Gilt das auch für die erweiterte These? Das ist mir nicht so ganz klar. Und dass der Geschichtsteil im Präsens formuliert ist, ist mir persönlich etwas zu literarisch. Ansonsten sehr schön! -- Sdo 01:31, 24. Okt. 2006 (CEST)

• pro: Sehr verständlich geschrieben. Boris Fernbacher 12:13, 25. Okt. 2006 (CEST)

• pro Sehr schön. Lediglich die Verlinkungen können verbessert werden. Das TSP ist gleich 4-mal verlinkt, die Landau-Symbole dagegen garnicht. Dann sollte man noch das Komplexiätsklassen-Schaubild etwas erläutern. --Tamás 00:06, 26. Okt. 2006 (CEST)

Die angesprochene Verlinkung habe ich mal behoben. Fühlt sich eigentlich irgendwer als Hauptautor für den Artikel zuständig? -- Sdo 00:53, 27. Okt. 2006 (CEST)

•  Pro interessanter, sehr verständlich geschriebener Artikel--Stephan 06:06, 5. Nov. 2006 (CET)

•  Pro Fachlich gut und scheinbar fehlerlos. Laienverständlichkeit kann ich als Fachmann nicht beurteilen, mit den geschichtlichen Details kenne ich mich auch nicht aus. Ich habe kleinere stilistische und orthografische Korrekturen angebracht und die von Sdo bemängelte Aussage zur erweiterten Church-Turing-These ausgebaut. --Bitbert 14:19, 6. Nov. 2006 (CET)
• neutral: Der Artikel gibt einen guten Ueberblick ueber die Komplexitaetstheorie, ist aber in einigen Bereichen zu ungenau.

Ich habe einige Anmerkungen dazu: Mir ist nicht bekannt, wo in der Komplexitaetstheorie endliche Automaten oder Kellerautomaten verwendet werden, sie tauchen auch im Artikel nicht mehr auf. Meiner Meinung beziehen sich die vorgestellten Hierarchiesaetze und Platz bzw. Zeitklassen alle auf Turingmaschinen. Es fehlt die Komplexitaetsklasse LINSPACE die genau den Typ 1 Sprachen entspricht. Bei der Unterscheidung von P und NP es sind nur die Probleme wirklich schwer, die in NP ohne P liegen, falls eine Trennung gefunden wird, mehrmals im Text ist davon die Rede, dass Probleme in NP schwer sind, aber ganz P liegt in NP! Damit ist auch die Ueberschrift zu NP "Praktisch (vermutlich) nicht lösbare Probleme" irrefuehrend. Im Abschnitt P = NP, folgt trivialerweise, dass ein polynomieller Algorithmus existiert, wenn P = NP gilt, aber er ist dann nicht unbedingt bekannt. Sicher ist, dass nicht alle Probleme in NP oder auch nur in P mit einem polynomiellen Zeitaufwand mit maximalem Exponenten 1000 geloest werden koennen.--Hardy

Meines Wissens nach sind durchaus bereits Algorithmen bekannt, die unter der Bedingung P=NP ein NP-vollständiges Problem in polynomieller Zeit lösen! Außerdem kann man leicht zu beliebig großem Exponenten ein Problem konstruieren, das sowohl in P liegt als auch mindestens ein Polynom mit entsprechendem Exponenten für die Laufzeit benötigt. --Koethnig 01:34, 14. Nov. 2006 (CET)

•  Neutral Für ein Kontra ist der Artikel einfach zu gut, aber ein paar Dinge stören mich. Der zweite Absatz im Abschnitt "Hierarchiesätze" ist für mich unverständlich, ebenso wäre eine kurze Einführung (mindestens aber ein Wikilink) in die Theorie der Maschinen wünschenswert. Ansonsten: Gelungen, kann uns gern als exzellenter Artikel vertreten. --Scherben 22:32, 6. Nov. 2006 (CET)

• Hardy: „Es fehlt die Komplexitaetsklasse LINSPACE[…]“—Nicht nur die. Hab nur quergelesen, aber mir fehlten spontan FP, FNP, TFNP, L/poly, P/poly, ⊕P, #P und noch ein paar andere. Das PCP-Theorem fehlt, ein Hinweis auf die verschiedenen Reduktionen auch. Ebenso im Geschichtsteil wichtige Ansätze, mit denen die P=NP-Frage attackiert wurde (etwa OTMs, iirc war auch Resolution mal ’ne Weile ein Hoffnungsträger für einen Beweis). —mnh·∇·₰!· 08:54, 8. Nov. 2006 (CET)

Literaturangaben nicht exzellent

Wie der Artikel mit Literaturverzeichnis (Stand 15. Nov. 2006) als Excellent ausgezeichnet wird, kann ich nicht verstehen. Nicht nur, dass die Regeln aus Wikipedia:Literatur#Format nicht verwendet sind, enthält die Liste Fehler, die offensichtlich unbesehen aus der englischsprachigen WP-Artikelfassung übernommen wurden. --KaPe, Schwarzwald 22:38, 2. Dez. 2006 (CET) Im Einzelnen:

Ungültige ISBN, falscher Titel

• M. Sipser: Time Complexity, Introduction to the Theory of Computation, 2. Auflage, Thomson Course Technology, 2006, ISBN 0-534-95097

"Time Complexity" gehört nicht zum Buchtitel; ISBN ist 9- statt 10-stellig, die vollständige ISBN 0-534-95097-3 bezieht sich auf eine Ausgabe von 2005; während 2006 eine internationale Ausgabe erschien mit anderer ISBN. Dass der Vorname des Autors und der Verlagsort fehlt, teilt dieser Eintrag mit einigen weiteren:

Fehlende Vornamen und Verlagsorte

• C. Papadimitriou: Computational Complexity, Addison-Wesley, 1993, ISBN 0-201-53082-1
• J. van Leeuwen: Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, The MIT Press/Elsevier, 1990, ISBN 0-444-88071-2
• M. R. Garey, D. S. Johnson: Computers and Intractability: A guide to the theory of NP-completeness, W.H. Freeman & Company, 1979, ISBN 0-716-71045-5

Reihenfolge Vorname - Name

• Du, Ding-Zhu, Ko, Ker-I: Theory of Computational Complexity, John Wiley & Sons, 2000, ISBN 0-471-34506-7

Zeitschriftenartikel, fehlende Angaben

• J. Hartmanis, R. E. Stearns: On the computational complexity of algorithms, Trans-American Mathematical Society, 1965

Veraltete Auflage

• K. Rüdiger Reischuk: Komplexitätstheorie - Band I: Grundlagen, B. G. Teubner Stuttgart - Leipzig, 1994, ISBN 3-519-12275-8

Die Bibliothekskataloge verzeichen mit Erscheinungsjahr 1999 eine: 2., völlig neubearb. und erw. Aufl.

Hab das Buch selber und die Daten stimmen, außer dass es halt die 2. völlig neubearb. und erw. Aufl. von 1999 ist. Man darf die Jahreszahl also gerne ändern! --Koethnig 23:27, 4. Dez. 2006 (CET)

Nicht erschienenes Buch

• van Dalen, Dawson, Kanamori (Hrsg.): The History of Mathematical Logic, North-Holland - Amsterdam, 2002/2003

Mir scheint, dieser Titel ist überhaupt nicht erschienen. Er scheint nur als Ankündigung zu existieren bei:

• L. Fortnow, S. Homer: A Short History of Computational Complexity, aus van Dalen, Dawson, Kanamori: The History of Mathematical Logic, North-Holland - Amsterdam, 2002/2003

Dieser Beitrag (abstract hier) ist online verfügbar (PDF, 218kB) und dort wird im Text hingewiesen auf an upcoming North-Holland Handbook of the History of Mathematical Logic, die herausgeben werde von Dirk van Dalen, John Dawson and Aki Kanamori.

Ein solches Buch gibt es nicht. Bei Aki Kanamori findet sich ein Hinweis, dass er Mitherausgeber wird von

„Volume 6 of the Handbook for the History of Logic, Sets and Extensions in the Twentieth Century, with Dov Gabbay and John Woods, to appear.“ (Kurzlebenslauf Aki Kanamori, PDF)

Beim Mitherausgeber John Woods findet sich eine Liste der Bände und Beiträge, demzufolge der Artikel von Fortnow/Homer Teil sein wird von Volume 9. Bis 2006 aind drei von elf geplanten Bänden erschienen, Band 9 gehört nicht dazu.

Diskussion aus dem Review (Dezember 2006 - Februar 2007)

Beim Abarbeiten der Liste formal falscher ISBN begegne ich vielen uneinheitlich formatierten Literaturangaben. Bei diesem Artikel, der mit Lesenswert (Januar 2006) und Exzellent (Nov. 2006) ausgezeichnet wurde, stieß ich auf ein fragwürdiges Literaturverzeichnis, siehe Diskussion:Komplexitätstheorie#Literaturangaben nicht exzellent, eingefügt direkt vorBeginn der Exzellenz-Diskussion. Gibt es Regeln, in wieweit die Formatierungsregeln vor einer Auszeichnung zu beachten sind? Angesichts der aus en:Computational complexity theory kopierten Fehler überlege ich, warum so etwas bei unserem Review- bzw. Auszeichnungsprozederes durchgehen kann. --KaPe, Schwarzwald 23:21, 2. Dez. 2006 (CET)

Nicht nur du stellst Fragen. Ich frage mich beispielsweise, wieso es für die Formatierung von Literaturangaben keinen Textbaustein gibt (kann zwar inhaltliche Fehler nicht vermeiden, aber vielleicht die Anzahl der "Formfehler" verringern).

Vielleicht ist auch vielen einfach das Tool zur wikifizierten Ausgabe eines Buchs mit der ISBN nicht bekannt?

Außerdem frage ich mich, wieso die dt.Wiki von anderen "Standardformatierungen" abweicht? Fragen über Fragen?La Corona 03:11, 1. Feb. 2007 (CET)

Gibt es: Vorlage:Literatur --Phrood 03:18, 1. Feb. 2007 (CET)

Problemgrößen

"Da es jedoch in der Regel unendlich viele Instanzen gleicher Größe für ein Problem gibt,..." Stimmt das? Gibt es für Instanzen der Größe n nicht nur endlich viele Möglichkeiten (beim Alphabet {0,1} nämlich 2^n)? JaK 11:46, 21. Mär. 2007 (CET)

Kommt auf den Bebriff der Problemgröße an. Formal (sprich: für beliebige - auch nicht-numerische - Probleme) wurde die eingeführt als Wortlänge der Probleminstanzbeschreibung über dem Alfabet {0,1}, so dass du recht hättest. Andererseits wird als Beispiel permanent das TSP durchdiskutiert und als dessen Problemgröße die Anzahl N der Knoten genommen. Hier hat man dann natürlich unendlich viele Instanzen zu einer Problemgröße, da man ja die Länge der einzelnen Matrixeinträge vernachlässigt. Man könnte sagen, das ist so zwar falsch , aber sinnvoll. Sonst müßte man ja sich auch einigen, wie genau man die Matrix codiert: N gefolgt von N*N Zahlen? N*N Zahlen gefolgt von einem "Sentinel"? Ohnehin nur N*(N-1)/2 statt N*N Zahlen? Wenn man später als Kostenfunktion für den Algorithmus ohnehin eine Addition oder Multiplikation zum Preis 1 veranschlagt (unabhängig von der Größe der Operanden), ergibt es üblicherweise keinen Sinn, Zahlen in der Eingabe anders als mit 1 zu bepreisen.--Hagman 10:29, 26. Apr. 2007 (CEST)

Quantencomputer und NP

Für solche Maschinen wird eine unbeschränkte Parallelisierbarkeit der sich verzweigenden Berechnungspfade angenommen, die technisch nicht realisiert werden kann. [...] auf der Basis eines unrealistischen Maschinenmodells.

Ließen sich mit Quantencomputern nicht NP-Algorithmen in polynomialer Zeit lösen (einige/alle)? Solche können wohl prinzipiell technisch realisiert werden, auch wenn der aktuelle Entwicklungsstand von einer nutzbaren Realisierung noch weit entfernt ist. 194.138.18.132 12:51, 25. Apr. 2007 (CEST)

Da alle Probleme in P auch in NP liegen, lassen sich sogar auf klassischen Computers einige NP-Probleme in polynomialer Zeit lösen :-) Es gibt aber ein berühmtes NP-Problem, für das kein klassischer polynomieller Algorithmus bekannt ist (das also möglicherweise kein P-Problem ist), das aber auf einem Quantencomputer in polynomieller Zeit gelöst werden kann: Die Primfaktorzerlegung (siehe Shor-Algorithmus). Das ist ein Hinweis, dass Quantencomputer tatsächlich einige NP-Probleme, die nicht in P liegen, in polynomieller Zeit lösen können. Definitive Aussagen kann man hier natürlich nicht erwarten, da sonst das P=NP-Problem ja gelöst wäre (denn die Existenz eines von Quantencomputern in polynomieller Zeit lösbaren NP-Problems, das kein P-Problem ist, würde ja bereits implizieren, dass P≠NP ist.) --Ce 14:44, 26. Apr. 2007 (CEST)

Falls die ursprüngliche Frage lauten sollte: "Gibt es NP-vollständige Probleme, die auch unter Annahme von P≠NP von Quantencomputern in polynomieller Zeit gelöst werden können", dann ist das wohl offen. Siehe z.B. http://dabacon.org/pontiff/?p=1489 --GrGr 16:09, 26. Apr. 2007 (CEST)

Der Fall P=NP

Aus dem Artikel:

Da Algorithmen bekannt sind, die NP-vollständige Probleme unter der Prämisse P = NP in Polynomialzeit lösen, wäre auf einen Schlag für sämtliche Probleme, die bekanntermaßen in NP liegen, auch ein polynomieller Algorithmus bekannt.

Gibt's dafür eine Quelle? Dass im Falle P=NP Polynomialzeitalgorithmen für NP-vollständige Probleme existieren, ist klar. Aber dass diese auch bekannt wären, ist mir neu. Siehe auch William Gasarchs P=?NP Poll Abschnitt 2.3 Punkt 4, Abschnitt 3 Kommentar 26 und Abschnitt 4 Punkt 6.

Auch im Artikel P-NP-Problem steht keine solche Behauptung. --GrGr 15:41, 26. Apr. 2007 (CEST)

Ein klassische Beweisverfahren dafür, dass ein Problem in NP liegt, besteht doch - wenn ich mich recht erinnere - darin, einen Algorithmus anzugeben, der es auf ein anderes Problem reduziert, von dem man schon weiß, dass es in NP liegt. Wenn man also für ein NP-vollständiges Problem einen Polynomzeitalgorithmus hat, dann auch für alle, die man auf dieses Problem reduzieren konnte. Insofern scheint mir die Behauptung aus dem Artikel auf den ersten Blick plausibel.

Andererseits ist mir nicht klar, ob das wirklich das einzige Beweisverfahren ist: z.B. für Faktorisierung gibt es die hübsche Argumentation, dass man die nichtdeterministische Turing-Maschine "einfach die richtige Faktorisierung erraten" lässt, das Produkt bildet und feststellt, dass man fertig ist. Dieser Ansatz bedürfte natürlich noch einer Formalisierung, um als Beweis durchzugehen, aber ich denke, es ist hinreichend klar, dass man das hinbekommen kann. Offensichtlich ist dies eine ganz andere Vorgehensweise als die Reduktion des Problems auf ein NP-vollständiges Problem. Wie man für Probleme, die man mit einer solchen Argumentation als zur Klasse NP gehörend identifiziert hat, einen Polynomzeitalgorithmus konstruieren kann, wenn man P=NP bewiesen hat, ist mir auch nicht klar. --213.218.25.130 20:19, 26. Apr. 2007 (CEST)

″Ein klassische Beweisverfahren dafür, dass ein Problem in NP liegt, besteht doch - wenn ich mich recht erinnere - darin, einen Algorithmus anzugeben, der es auf ein anderes Problem reduziert, von dem man schon weiß, dass es in NP liegt.″

Das kann man tun: $(A\leq _{p}B\wedge B\in \mathrm {NP} )\Rightarrow A\in \mathrm {NP}$, ist aber nicht gerade üblich.

″Wenn man also für ein NP-vollständiges Problem einen Polynomzeitalgorithmus hat, dann auch für alle, die man auf dieses Problem reduzieren konnte.″

Auch das ist richtig. Alle Probleme, die man auf ein NP-vollständiges Problem reduzieren kann, sind übrigens per Definition genau alle Probleme in NP.

″Insofern scheint mir die Behauptung aus dem Artikel auf den ersten Blick plausibel.″

Das ist die falsche Folgerung. Falls jemand einen Beweis für P=NP findet, muss das eben nicht heißen, dass er einen Polynomialzeitalgorithmus für irgendein NP-vollständiges Problem hat. Es kann auch eine völlig andere Methode sein. Siehe die Quelle William Gasarchs P=?NP Poll, in der anerkannte Informatiker ihre Vermutungen zur Lösung des P-NP Problems angeben.

Gestern hat sich ja sogar jemand erbarmt, das zu ändern. Vielen Dank. -- GrGr 08:32, 14. Mai 2007 (CEST)

Das mag stimmen, aber soweit mir bekannt ist, gibt es Algorithmen, von denen man zeigen kann, dass sie unter der Bedingung P=NP ein NP-vollständiges Problem in polynomieller Zeit lösen. Insofern hat man dann also schon automatisch einen solchen Algorithmus! --Koethnig 23:52, 14. Mai 2007 (CEST)

ich meine auch das mal gehört zu haben; kann mich aber auch täuschen. Dazu wäre ne Quelle schön, kennt niemand eine?--Spid 20:28, 25. Mai 2007 (CEST)

Kann ich mir ehrlich gesagt nicht vorstellen. Entweder es gilt P=NP oder P!=NP. Im ersten Fall hieße das ja, dass wir einen Polynomialzeitalgorithmus haben, den wir nur nicht gut genug analysieren können. Nicht, dass es sowas nicht geben kann, siehe z.B. Manindra Agrawal, der für seinen Primzahltest auch verschiedene mögliche Polynom-Grade der Laufzeit angibt, je nachdem, ob mathematische Vermutungen stimmen. Sollte da was dran sein, wären natürlich für alle NP-vollständigen Probleme Polynomialzeitalgorithmen bekannt. Man braucht ja nur die Reduktionen davor zu schalten. Also bitte eine Quelle!! --GrGr 18:24, 28. Jun. 2007 (CEST)

If I understand the question properly, the question is answered here: en:P_versus_NP_problem#Polynomial-time_algorithms. --RobinK 19:03, 13. Dez. 2009 (CET)

Der Weblink auf den Complexity Zoo funktioniert nicht mehr

Er sollte wohl hier

http://qwiki.stanford.edu/wiki/Complexity_Zoo

hinzeigen, aber ich weiß nicht, wie man das macht. Ich verstehe den Quellcode des Abschnitts "Weblinks" nicht. Sorry. Wikiplex 14:34, 27. Nov. 2008 (CET)

Erledigt. --MRA 21:21, 27. Nov. 2008 (CET)

Die Klasse NP: Praktisch (vermutlich) nicht lösbare Probleme

Die Probleme in NP gelten daher für praktische Zwecke als nicht lösbar:

Für die Praxis gibt es für viele Probleme (z.B. das Problem des Handlungsreisenden) Verfahren, die gute Näherungen berechnungen. Diese Näherungslösungen sind für die Praxis völlig ausreichend. --Bri B. 11:47, 15. Feb. 2010 (CET)

Der Absatz ist (so formuliert) sowieso grundfalsch. Probleme in NP sind nicht grundsätzlich schwer, denn die Klasse NP enthält u.a. die Klasse P. Allerdings enthält NP (im Gegensatz zu P) eben zusätzliche Probleme, die (unter der Voraussetzung P!=NP) beweisbar nicht mehr in polynomieller Zeit (von einer Turingmaschine) zu lösen sind. Dieser Fehler wird oft gemacht, gemeint sind meist die NP-vollständigen Probleme (genauer: die stark NP-vollst. Probleme). Auch gibt es in der Polynomiellen Hierarchie viele noch "schwerere" Klassen. (nicht signierter Beitrag von 89.245.111.148 (Diskussion) 12:31, 5. Jul 2011 (CEST))

ich habe mal das groebste korrigiert. der abschnitt soll mMn nur eine intuition vermitteln, da moechte ich approxmative algorithmen nicht erwaehnen. mit der deutung von "loesen" als "exakt loesen" ist der abschnitt aber nicht falsch. --Mario d 13:15, 9. Jan. 2012 (CET)

Ich fürchte hier ist noch einiges im Argen. Zum ersten ist ja P in NP enthalten und damit gibt es ja sehr wohl Probleme aus NP die sich effizient lösen lassen. Das wird erst im letzten Satz erwähnt, voerher wird allerdings etwas anderes suggeriert. Zum zweiten: gleich am Anfang heißt es Die Algorithmen zur Lösung der Probleme in NP basieren auf einem nichtdeterministischen Maschinenmodell. Was soll denn hier eigentlich in diesem Zusammenhang die Algorithmen heißen? Es gibt ja nun bekanntlich auch für jedes Problem aus NP einen Algorithmus der durch ein deterministisches Programm beschrieben wird. Die etwas schwammig formulierte Parallelisierbarkeit kann halt doch realisiert werden (wenn auch mit hoher Laufzeit). Die Bezeichnung praktisch nicht lösbar halte ich auch für zweifelhaft. Man bedenke nur, wieviele Probleme heutzutage technisch mit Hilfe eines SAT solvers gelöst werden. Vielleicht sollte man den ganzen Abschnitt umschmeißen - und eher über die effiziente Verifizierbarkeit die Klasse NP definieren. Dies ist in aktuellen Lehrbüchern der favorisierte Weg, wie man die Klasse NP einführt. --Andreschulz (Diskussion) 20:39, 12. Feb. 2014 (CET)

ich finde auch, dass die ueberschrift in dieser form irrefuehrend ist. vielleicht sollte man den zusatz nach dem doppelpunkt einfach loeschen. in der einleitung von NP (Komplexitätsklasse) ist doch eine ganz nette beschreibung, vielleicht koennte man es hier so aehnlich machen und beides darstellen. --Mario d 11:54, 13. Feb. 2014 (CET)

Die Entscheidung, ob ein gegebenes Tripel zu dieser Sprache gehört, entspricht dem Lösen des Problems der Multiplikation zweier Zahlen.

Überprüfung des Ergebnisses dürfte auch bei Multiplikation wesentlich einfacher sein, als zu multiplizieren. Z.B. liefert kurzes Googlen hier einen Zeitunterschied: https://www.sciencedirect.com/science/article/pii/S0885064X09001150. Insofern sollte der Paragraph überarbeitet werden.--Jocme (Diskussion) 17:02, 17. Mär. 2018 (CET)