[Im folgenden gebe ich keine exakte Beschreibung von NP usw., wenn also mein Info-Prof das liest: Ich versuche, das einem Laien verständlich zu machen....]
Nein, das ist nicht korrekt. Zumindest wird das sehr stark vermutet.
Benötigt werden zum Verständnis von NP die nichtdeterministischen Turingmaschinen (NDTM). Das waren die, die möglicherweise Wahlmöglichkeiten in ihrem Programm haben und ein Problem lösen, wenn es eine Abfolge von Wahlen gibt, die zum Ziel führt. Und das ist der Knackpunkt beim Nichtdeterminismus, den man verstehen muss. Das Problem ist gelöst, wenn es eine Abfolge von "richtigen" Entscheidungen gibt. Wie diese gefunden werden, spielt gar keine Rolle. Man spricht da auch von einem "Entscheidungsbaum". Wenn es vom Start einen Weg durch diesen Baum gibt, der zum Ergebnis führt, dann reicht das, auch wenn es Millionen anderer Wege gibt, die in eine Endlosschleife führen oder es zu einer "Fehlermeldung" kommt...
Wenn es für ein Problem ein solche (theoretische) Maschine gibt, die das Problem in Polynomzeit löst, dann ist diese Problem in der Klasse NP. Das heißt: (N)ichtdeterministisch (P)olynomiell. In Polynomzeit heisst hier: Wenn ein "richtiger Weg" polynomiell viele Schritte lang ist.
Wenn es eine deterministische Turingmaschine (DTM) gibt (also eine, die eher unseren Computern und den Programmen entspricht, also eine ohne diese Art Wahlmöglichkeiten), die das Problem in Polynomzeit löst, dann ist das Problem in der Klasse P.
Es ist bis heute unbekannt, ob P=NP, oder P "ungleich" NP. Daher ist deine Aussage "Es sind Probleme welche sich nicht in polynomineller Zeit lösen lassen" falsch, weil man es noch nicht weiss (obwohl fast alle davon ausgehen). Außerdem lassen sie sich ja in Polynomzeit lösen, aber eben mit einer nichtdeterministischen Turingmaschine.
Ausserdem: Jede DTM ist auch eine NTDM, aber eben eine, die immer nur eine "Wahl zwischen einer Möglichkeit" hat. Somit ist jedes Problem in der Klasse P auch in der Klasse NP, d.h. es gibt viele Probleme in NP, die auch mit unseren Rechnern in Polynomzeit lösbar sind.
!!! NP heisst nicht "nicht polynomiell" !!!
--------------
Soviel erstmal dazu. Jetzt zur Polynomiellen Laufzeit. Das hat nix mit erfüllbar zu tun. Erfüllbar in Zusammenhang mit NP kann nur das SAT oder 3SAT Problem sein, wobei Boolsche Formeln erfüllbar sein sollen. (Hat nix mit Fernsehen zu tun, das sind zwei grundlegende "NP-vollständige" Probleme. Was genau NP-vollständig heisst, erklär ich später mal. Ganz kurz sind es die Probleme, für die man noch keinen polynomiellen Lösungsalgotithmus für eine DTM gefunden hat; also wahrscheinlich mit unseren Rechnern nicht polynomiell lösbar sind)
Ein Polynom ist ein Ding der Form p(x)=a_n*x^n + a_{n-1}*x^{n-1} + ... + a_2*x^2 + a_1*x + a_0. Kennt man wohl aus der Schule, n ist dabei eine natürliche Zahl, z.b. 2, dann hat man eine Parabel.
Praktisch jeder Algorithmus verlangt ja eine Eingabe. Diese Eingabe hat ein gewisse Größe. Zum Beispiel möchte man ein paar Zahlen sortieren, 100, 1000, oder 10Millionen. Oder man möchte kürzeste Wege zwischen 2 bestimmten Städten aus 100 oder 10.000 Städten bestimmen. Diese Größe ist das "x" in dem Polynom. Das p(x) (oder meinetwegen das y), was am Ende rauskommt, sollte die Laufzeit (die Anzahl der Rechenschritte) sein.
Ein Algorithmus hat eine Polynomielle Laufzeit, wenn es ein Polynom gibt (d.h. ein n und die Vorfaktoren a_n ....a_1 und die Konstante a_0), so dass für jede beliebige Eingabegröße (bis auf ein paar kleine am Anfang) die Anzahl der Rechenschritte, die der Algorithmus benötigt kleiner oder gleich dem Wert p(x) ist.
Ein ganz einfaches Beispiel:
Quelltext
1: 2: 3: 4: 5: 6: 7: 8:
| Eingabe: ein Zahlen-Array A mit x vielen Einträgen Aufgabe: Suche das kleinste Element
min:=A[1] (1 Schritt) für alle i:=2,....,x do wenn A[i] < min dann min:=A[i] (x-1 Schritte)
Ausgabe: min (1 Schritt) |
Das Ding hat offensichtlich eine Polynomielle Laufzeit. Wähle z.B. n=1, a_1=1 und a_0=1. In diesem Fall (n=1) spricht man auch von linearer Laufzeit.
Ich hoffe, ich konnte da etwas weiterhelfen...
We are, we were and will not be.