Diskussion:Komplexitätsklasse

alte Diskussionen

Kann vielleicht mal jemand zunächst erklären, was Nichtdeterministisch ist, das ist für das gesamte Verständnis wesentlich? -- Nichtich 20:45, 19. Apr 2004 (CEST)

Nichtdeterminismus sollte dringend geschrieben werden, und die Komplexitätsklassen könnte man auch einfacher erklären/vorstellen. Bei Gelegenheit! --Pinguin.tk 23:08, 17. Mai 2004 (CEST)

<lob> wow, geniale Beispiele! Bin selber Physikstudent, weiss aber, wie blöd man (frau) vor unverständlichen mathematischen erklärungen sitzt. </lob> Endymi0n 12:50, 4. Aug 2005 (CEST)

Ich kenne eine andere Definition von Komplexitätsklassen:

Eine Komplexitätsklasse ist meines Wissens einfach nur eine Menge von Entscheidungsproblemen (oder formalen Sprachen, je nach Sichtweise).

Die bekanntesten Komplexitätsklassen sind definiert als Mengen von Entscheidungsproblemen, die sich von einer Turingmaschine (oder einer Registermaschine) in einer bestimmten maximalen Anzahl an Rechenschritten ("Zeitkomplexität") oder mit einer bestimmten maximalen Menge an Rechenschritten ("Speicherkomplexität") in Abhängigkeit von der Länge der Eingabe entscheiden lassen.

Z.B. P als die Menge der formalen Sprachen, für die es ein Polynom f(n)=a_n*x^n+...+a_1*x+a_0 gibt, so dass eine deterministische Turingmaschine gibt, die für jedes Wort einer Länge n innerhalb von f(n) Rechenschritten entscheiden kann, ob das Wort in der Sprache liegt. (vielleicht auch als Menge der deterministischen Turingmaschinen, die nach f(n) Rechenschritten auf jeden Fall angehalten haben)

132.231.1.58 13:05, 6. Sep. 2007 (CEST)

DTIME(t(n)) c DSPACE(t(n)

Unter der Überschrift "Zusammenhänge" ist ein Bildchen mit "DTIME(t(n)) c DSPACE(t(n)". Das ist zwar hübsch, aber mir völlig unverständlich (was ist DTIME/DSPACE? Was ist t()? Und was für ein n?), und hat überhaupt keinen erkennbaren Zusammenhang mit dem Artikel. Oder ist der Zusammenhang offensichtlich und erschließt sich nur mir nicht mangels Vorbildung?

Was die Namen bedeuten, kannst du unter Liste von Komplexitätsklassen erfahren. Ich stimme dir aber zu, dass dieser Abschnitt ohne jede Erklärung hier fehl am Platz ist, zumal es ein sehr willkürlich herausgegriffenes Beispiel ist. Ich nehme es mal heraus --Plotterfreund 20:32, 11. Dez. 2007 (CET)

Klasse von Problemen oder Algorithmen

Der Artikel ist hier ein wenig unklar. Es wird davon geredet, dass eine Komplexitätsklasse eine Klasse von Problemen bzw. Algorithmen ist. Das halte ich aber für sehr ungenau. Wenn ich mich an mein Studium erinnere (und mir auch die Definition von NP in der Wikipedia anschaue), dann wird von Problemklassen geredet.

Was ist der Unterschied? Nehmen wir das SAT-Problem: es gibt natürlich einen Algorithmus, der SAT in einer Zeit entscheidet, die schlechter als EXPTIME bzw. NP ist. Trotzdem liegt SAT in NP. Meines Wissens ist das aber völlig uninteressant, weil man sich immer für den besten, bekannten Algorithmus interessiert, um ein Problem zu klassifizieren und nicht um ALLE Algorithmen.

Aus dem Grund lautet die Definition immer "Das Entscheidungsproblem für Sprache L liegt in Klasse X, falls es ein TM gibt, die die Sprache L in der Zeit x(l) entscheidet"

Kann das mal ein Theoretiker überprüfen? (nicht signierter Beitrag von 87.170.189.168 (Diskussion | Beiträge) 00:40, 15. Jul 2009 (CEST))

Komplexitätsklassen sind Mengen von Problemen und nicht von Algorithmen. Ein Algorithmus kann evtl. bezeugen, dass ein bestimmtes Problem in einer Klasse liegt. Das ändert aber nichts an der Tatsache, dass Komplexitätsklassen Mengen von Problemen sind. Probleme wiederum sind als Sprachen kodiert [1] Ich ändere das um, da es sonst zu extremer Verwirrung im Artikel führt. Andreschulz (Diskussion) 13:29, 27. Apr. 2013 (CEST)

Falsches Beispiel

In meinen Augen ist das Beispiel für die Reduktion falsch. Einerseits wird ein lineares Problem genommen und dann ein zweites mit Laufzeiten n bzw. log n. Erstesns ist log n nicht "die Hälfte" von n. Zweitens handelt es sich bei einer Reduktion nicht um ein verkleinern des Problems sondern um eine Umformung. Hierzu ist eine formale Formulierung des Problems und eine Umformung des Problems A in das Problem B notwendig.

Zudem ist eine polynomielle Reduktion von einem großen Problem auf ein kleineres nicht möglich - sonst würde man wiederlegen, dass das "größere" Problem groß ist, sondern nur so groß wie das Problem auf das die Reduktion stattgefunden hat. Wäre die Reduktion wie im Beispiel "erfolgreich" wäre bewiesen, dass ein Problem der Laufzeit n auch in der Laufzeit log n lösbar wäre. Was offensichtlich nicht der Fall ist. (nicht signierter Beitrag von Error predator (Diskussion | Beiträge) 19:53, 6. Apr. 2012 (CEST))