Komplexitätsklassen

[freakC++]

Hallo zusammen,

ich habe verschiedene Fragen zu Komplexitätsklassen.

1.) Gibt es einen Algorithmus, der in die NL - Klasse fällt?

2.) Ich weiß, dass der wort-case von BubbleSort $$\frac{n \cdot (n-1)}{2}$$ ist. Warum gehört dann der BubbleSort zur Komplexitätsklasse P, obwohl diese eine Untergrenze von log(x) hat? Außerdem hat P eine Obergrenze von n, der BubbleSort hat jedoch einen worst case von n^2. n^2 wächst aber schneller als n und ist daher noch schlechter als P, oder? Für mich würde es eher Sinn machen, wenn es hieße, dass die Obergrenze von P ein Polynom sei und genau n.
(Ich habe sowas Ähnliches schonmal gefragt, aber ich komme gerade wieder durcheinander)

Vielen Dank
lg, freakC++

[volkard]

Zu 2)
Verstehe die Frage nicht. Was gefällt Dir an http://de.wikipedia.org/wiki/P_(Komplexitätsklasse) nicht?

[CStoll]

freakC++ schrieb:

1.) Gibt es einen Algorithmus, der in die NL - Klasse fällt?

praktisch anwendbare nichtdeterministische Algorithmen gibt es eher weniger, aber es gibt Probleme in dieser Klasse.

2.) Ich weiß, dass der wort-case von BubbleSort $$\frac{n \cdot (n-1)}{2}$$ ist. Warum gehört dann der BubbleSort zur Komplexitätsklasse P, obwohl diese eine Untergrenze von log(x) hat? Außerdem hat P eine Obergrenze von n, der BubbleSort hat jedoch einen worst case von n^2. n^2 wächst aber schneller als n und ist daher noch schlechter als P, oder? Für mich würde es eher Sinn machen, wenn es hieße, dass die Obergrenze von P ein Polynom sei und genau n.

Genau das heißt P - die Laufzeit ist begrenzt durch ein Polynom n^k für eine Konstante k aus N. Woher du diese n und log n hast, solltest du mal erklären (vermutlich etwas durcheinandergebracht).

[freakC++]

CStoll schrieb:

Genau das heißt P - die Laufzeit ist begrenzt durch ein Polynom n^k für eine Konstante k aus N.

Achso. Das heißt es geht hier um ein Polynom. Sobald ein Algorithmus einen worst Case in Forme eines Polynoms hat (z.B. InsertionSort) gehört es zur Klasse P. Falls eine nichtdeterministische Turingmaschine gebraucht wird, um das Problem zu lösen, gehört es zu NP.

CStoll schrieb:

Woher du diese n und log n hast, solltest du mal erklären (vermutlich etwas durcheinandergebracht).

In der Schule haben wir uns die Komplexitätsklassen näher angeschaut und zu jeder die O und die Omega Notation aufgeschrieben, also den worst- und den best-case. Es hieß, dass der beste Fall Omega(log(n)) und der schlechteste O(n) sei. Wahrscheinlich also O(p(n)).

[CStoll]

freakC++ schrieb:

In der Schule haben wir uns die Komplexitätsklassen näher angeschaut und zu jeder die O und die Omega Notation aufgeschrieben, also den worst- und den best-case. Es hieß, dass der beste Fall Omega(log(n)) und der schlechteste O(n) sei. Wahrscheinlich also O(p(n)).

Der beste oder schlechteste Fall wovon ist denn hier gemeint? Solche konkreten Grenzen gibt man normalerweise für einen bestimmten Algorithmus an und wirft sie nicht einfach in den Raum.

[freakC++]

Von der Komplexitätsklasse. Alle Probleme, die sich in dieser Klasse befinden, haben diese Eigenschaften. So haben wir es gelernt. Mit besten / schlechtesten Fall meine ich den worst-/best case.

[CStoll]

Erstmal interessiert bei den meisten Betrachtungen nur die Obergrenze der Laufzeit. Und zweitens sind die möglichen Grenzen für Algorithmen einer Komplexitätsklasse sehr weit gesteckt - selbst ein Algorithmus mit Laufzeit O(n¹⁰⁰⁰) liegt noch in P.
Bei einem konkreten Algorithmus wird dann mitunter präziser eingeordnet, um die Unterschiede bei gleicher Aufgabe (z.B. Sortien von Arrays) erfassen zu können.

[freakC++]

Das ist klar. Trotzdem kann man ja den worst case und den best case einer Klasse so allgemein beschreiben. Damit ist zum Beispiel klar, dass ein Problem niemals in logarithmischer Zeit lösbar ist.

[CStoll]

freakC++ schrieb:

Das ist klar. Trotzdem kann man ja den worst case und den best case einer Klasse so allgemein beschreiben. Damit ist zum Beispiel klar, dass ein Problem niemals in logarithmischer Zeit lösbar ist.

Worst case und best case machen nur Sinn in Bezug auf ein gegebenes Problem (oder gar einen gegebenen Algorithmus) - und beziehen sich dann meist auf die Eingaben, mit denen er besonders gut oder schlecht zurechtkommt.
Bei Problemen kannst du abschätzen, wieviele Operationen du mindestens benötigst, um ein korrektes Ergebnis zu erzielen (z.B. kann bewiesen werden, daß Sortieren durch Vergleich und Austausch nicht besser als O(n log n) sein kann). Bei einzelnen Algorithmen kannst du analysieren, für welche Eingaben sie besonders gut oder schlecht geeignet sind.

Eine Komplexitätsklasse ist eine Menge von Problemen, die so wenig miteinander zu tun haben, daß es keinen Sinn macht, sie miteinander zu vergleichen.

[Gregor]

freakC++ schrieb:

Das ist klar. Trotzdem kann man ja den worst case und den best case einer Klasse so allgemein beschreiben. Damit ist zum Beispiel klar, dass ein Problem niemals in logarithmischer Zeit lösbar ist.

Best Case macht da nur wenig Sinn, denn mit den Komplexitätsklassen sieht es ungefähr so aus (ich beschränke mich hier auf nur ein paar und lasse ungefähr 100 weg):

$\text{L} \subseteq \text{NL} \subseteq \text{P} \subseteq \text{NP} \subseteq \text{PSPACE} \subseteq \text{EXP} \subseteq \text{NEXP}$

Das heißt, zwischen den einzelnenen Komplexitätesklassen bestehen Teilmengen-Beziehungen. Bei einigen weiß man auch, dass die Mengen nicht gleich sein können, zum Beispiel ist P eine echte Teilmenge von EXP. Aber es macht dann keinen Sinn, von einem Best Case für eine Klasse zu reden: Jedes Problem in NL ist auch in P.

[freakC++]

Dann werde ich nicht mehr von einem worst- oder best-case einer Klasse reden. Ich soll aber über die "Komplexitätsklassen POLY und NPOLY" bescheid wissen.

Vielleicht stelle ich mich auf nur doof an, aber was sind das für Klassen. Ich kenne L, NL, P, NP, EXPTIME, NEXPTIME, EXPSPACE, NEXPSPACE. Was ist aber POLY?

Danke
lg, freakC++

[ipsec]

Vom Namen her würde ich denken, es sind P und NP gemeint.

[freakC++]

Das würde Sinn machen. Dann hoffe ich einfach mal, dass das richtig ist.

Ich habe noch eine andere Frage. Im Unterricht sagten wir, dass die Lineare Suche in die Komplexitätsklasse P gehöre. Ich weiße, dass die Unterschranke von P der Logarithmus ist und die Oberschranke ein Polynom. Bei der Linearen Suche ist es aber so, dass das gesucht Element gleich am Anfang liegt. Der best-case wäre also Omeaga(1). Das würde aber nur zur Komplexitätsklasse L passen. Was ist jetzt richtig?

Ich danke euch
lg, freakC++

[CStoll]

Um die Laufzeit eines Algorithmus einstufen zu können, darfst du nicht nur den optimalsten Fall betrachten, sondern alle möglichen Eingaben (im besten Fall ist BubbleSort auch schneller als QuickSort).

PS: Außerdem geht es bei L um den Platzbedarf - und ja, die lineare Suche dürfte imho auch in L liegen (sie braucht außer der Eingabe nur konstanten Speicherplatz).

[freakC++]

CStoll schrieb:

(sie braucht außer der Eingabe nur konstanten Speicherplatz).

Das bedeutet nur, dass der Algorithmus inplace arbeitet, aber sollte sich nicht auf die Komplexität auswirken.

CStoll schrieb:

Um die Laufzeit eines Algorithmus einstufen zu können, darfst du nicht nur den optimalsten Fall betrachten

Ich dachte, in diesem Fall ist es egal, weil wenn der optimalste Fall 1 ist, dann kann der Algorithmus gar nicht in P liegen, weil solche Probleme in L sind. Oder?

CStoll schrieb:

(im besten Fall ist BubbleSort auch schneller als QuickSort).

Stimmt! Trotzdem liegen beide in P, oder?

lg, freakC++

[Michael E.]

freakC++ schrieb:

Im Unterricht sagten wir, dass die Lineare Suche in die Komplexitätsklasse P gehöre.

Das ist korrekt. Wähle als Polynom p(x) = x.

Ich weiße, dass die Unterschranke von P der Logarithmus ist

Wer sagt denn sowas? Was soll überhaupt eine Schranke für eine Unterschranke sein? Auch Σ* liegt in P, obwohl es Algorithmen für diese Sprache mit Worst-Case-Laufzeit O(1) gibt (einfach immer sofort akzeptieren).

und die Oberschranke ein Polynom.

Auch hier wieder: Was soll eine Oberschranke für eine Klasse sein?

Selbst wenn man deine Aussage etwas anders interpretiert (so wie du sie wahrscheinlich gemeint hast), ist sie immer noch falsch: Es gibt kein Polynom p, sodass P = O(p).

Bei der Linearen Suche ist es aber so, dass das gesucht Element gleich am Anfang liegt. Der best-case wäre also Omeaga(1).

Best Cases interessieren hier nicht.

[freakC++]

Wenn ich einen Algorithmus habe und entscheiden möchte, in welcher Komplexitätsklasse er gehört, dann tue ich das anhand der Ober- und Untergrenze (O- und Omega-Notation). Wahrscheinlich ist das falsch, denn stoße dabei ja auf Widerstand. Ich dachte, dass die Lineare Suche eine Untergrenze (Omega) von 1 hat und daher in L gehört, weil wir uns das so aufgeschrieben haben. P kann bestensfalls logarithmisch sein. Das hatten wir uns ebenfalls aufgeschrieben.

Ist die Lineare Suche jetzt in P oder L. Ich bin weiterhin für L.

[CStoll]

freakC++ schrieb:

CStoll schrieb:

(sie braucht außer der Eingabe nur konstanten Speicherplatz).

Das bedeutet nur, dass der Algorithmus inplace arbeitet, aber sollte sich nicht auf die Komplexität auswirken.

Die Komplexitätsklasse L ist definiert über den Platzverbrauch (und mit der Bedingung, daß die Eingabe nicht überschrieben wird - darum sind auch InPlace-Sortieralgorithmen nicht in L).

CStoll schrieb:

Um die Laufzeit eines Algorithmus einstufen zu können, darfst du nicht nur den optimalsten Fall betrachten

Ich dachte, in diesem Fall ist es egal, weil wenn der optimalste Fall 1 ist, dann kann der Algorithmus gar nicht in P liegen, weil solche Probleme in L sind. Oder?

Erstens: Für die Laufzeit darfst du nicht nur die "guten" Eingaben betrachten, sondern ALLE möglichen Eingaben.
Zweitens: Wo ist hier der Widerspruch? L ist eine Teilmenge von P, damit liegt natürlich auch jedes L-Problem in den höheren Komplexitätsklassen.

CStoll schrieb:

(im besten Fall ist BubbleSort auch schneller als QuickSort).

Stimmt! Trotzdem liegen beide in P, oder?

Das auch - aber darauf wollte ich nicht hinaus.
Bei den Sortieralgorithmen geht es schon gar nicht um die Frage, ob sie nun polynomiell sind. In dem Bereich geht es schon um den Exponenten des Polynoms.

Im besten Fall hat BubbleSort eine Laufzeit von O(n) und QuickSort O(n log n), im schlechtesten Fall kommen beide auf O(n²). Für die allgemeine Betrachtung verwendet man aber meistens den durchschnittlichen Fall (da kommen die beiden Algorithmen auf O(n²) bzw O(n log n)), gelegentlich wird auch der worst-case oder die Proportionalitätskonstante hinter dem O() wichtig.
(btw, die besten und schlechtesten Fälle unterscheiden sich je nach Algorithmus ;))

[Michael E.]

freakC++ schrieb:

Wenn ich einen Algorithmus habe und entscheiden möchte, in welcher Komplexitätsklasse er gehört, dann tue ich das anhand der Ober- und Untergrenze (O- und Omega-Notation).

Der Algorithmus liegt nicht in den Komplexitätsklassen, sondern das Problem, welches er löst. Außerdem hast du von Ober- und Untergrenzen für Klassen und nicht für Algorithmen gesprochen. Desweiteren ist nur die Obergrenze interessant.

Ich dachte, dass die Lineare Suche eine Untergrenze (Omega) von 1 hat und daher in L gehört, weil wir uns das so aufgeschrieben haben. P kann bestensfalls logarithmisch sein. Das hatten wir uns ebenfalls aufgeschrieben.

Dann habt ihr euch was Falsches aufgeschrieben. Vielleicht meinst du P \ L oder etwas dergleichen.

Ist die Lineare Suche jetzt in P oder L. Ich bin weiterhin für L.

In beiden.