NP-vollständig

Computer: Software & Programmierung Programmierung allgemein
#1

Hi !

Ich lerne gerade auf Staatsexamen Mathematik, Teilprüfung Informatik. Jetzt habe ich von der Anschauung her ein Problem mit dem Begriff NP-vollständig.
Im Schöning steht, es würde intuitiv so viel wie „mindestens so schwierig, wie jedes andere Problem in NP“ heißen. Jetzt versuche ich es, mit meinen Worten zu konkretisieren:
Ein NP-vollständiges Problem besitzt für jede nichtdeterministische Turingmaschine und jedes Polynom ein Element der Länge n, dass nicht in O(p(n)) liegt, ist aber grundsätzlich für alle n polynomial beschränkt (müsste dann nicht das begrenzende Polynom von der Größe von n abhängen?)
Ich würde mir das dann so vorstellen, dass zum Beispiel die Rechenzeit aller Elemente der Länge

#2

Hallo,
das „mindestens so schwierig, wie jedes andere Problem in
NP“, umfaßt zwei Aussagen. Einerseits, daß das Problem
in NP liegt („andere“), andererseits, daß jedes Problem
in NP auf dieses Problem reduzierbar ist („mindestens
so schwierig“). Die Reduktion wiederrum, darf polynomialen
(Zeit)Aufwand haben. Deshalb ist durchaus gegeben, daß
ein NP-vollständiges Problem z.B. mit linearen Aufwand
(auf einer NTM) gelöst werden kann (z.B. das Erfüllbarkeits-
problem).

Gruss
Enno

#3

Ich habe weiterhin meine Probleme mit dem Begriff „mindestens so schwierig“. Das Erfüllbarkeitsproblem ist ein gutes Beispiel: Das Problem ist auf einer NTM ja nun wirklich ziemlich einfach (linear halt). Auf einer DTM dagegen hat es Laufzeit 2^n. Nur von DTM reden wir im Zusammenhang mit NP-Vollständigkeit ja nicht. Deshalb frage ich mich, was „mindestens so schwierig“ denn nun heißt.
Wenn ich nun ein Problem A habe, dass zum Beispiel eine Laufzeit von n^100 hat, ich dieses mit Laufzeit n^100 auf das Erfüllbarkeitsproblem reduzieren kann, dann ist doch A „schwieriger“ als das Erfüllbarkeitsproblem, da ich, egal auf welchem Weg, immer eine Laufzeit von n^100 habe. Oder wieso ist trotzdem SAT schwieriger???

Torsten

#4

Hallo,
„schwierig“ übersetzt man vielleicht besser mit „universell“.
Vollständige Probleme (btw es gibt auch P-Vollständigkeit)
haben halt die Eigenschaft im Sinne der „ist-schwieriger-als“
Ordnung Maxima zu bilden.
Ob eine DTM für SAT wirklich exponentielle Zeit benötigt ist
_das_ offene Problem der Informatik. Man weiß lediglich, daß
sich alle Probleme, die sich in polynomialer Zeit auf einer NTM
lösen lassen mit polynomialen „Mehraufwand“ auf dieses Problem
zurückführen lassen.
Könnte man z.B. SAT in O(n^100) lösen, wäre damit auch ein
kanonisches Lösungsverfahren gegeben, mit dem sich alle Probleme
in NP auch auf einer DTM in polynomialer Zeit lösen ließen.
Grob betrachtet wäre der Nichtdeterminismus damit kein
Mehrgewinn. Der Begriff der NP-Vollständigkeit dient bei dieser
Frage einfach dazu dazu konkrete Bsp. vor Hand zu haben und nicht über alle Elemente von NP argumentieren zu müssen.

Wenn ich nun ein Problem A habe, dass zum Beispiel eine
Laufzeit von n^100 hat, ich dieses mit Laufzeit n^100 auf das
Erfüllbarkeitsproblem reduzieren kann, dann ist doch A
„schwieriger“ als das Erfüllbarkeitsproblem, da ich, egal auf
welchem Weg, immer eine Laufzeit von n^100 habe. Oder wieso
ist trotzdem SAT schwieriger???

Zunächst die O-Maße geben obere Schranken an. Das vermeintliche
O(n^100) Problem ist vielleicht linear. SAT ist wie gesagt
„universeller“. Nimm z.B. die Multiplikation zweier Binärzahlen.
Hier wirst Du auch auf einer NTM mehr als linearen Aufwand
benötigen, während der Versuch beliebige Probleme in NP darauf
zu reduzieren (vermutlich) scheitert. SAT hat aber genau diese
Eigenschaft, obwohl es linear ist. Die Reduktion der
Multiplikation auf SAT ist dann sicher nicht-linear.
Anders ausgedrückt - der Versuch die „Schwierigkeit“ einfach
anhand der max. Exp. des Polynoms zu bemessen, scheitert daran,
daß bei den Reduktionen beliebiger polynomialer Mehraufwand
zulässig ist.

Gruss
Enno

#5

Danke, Enno, ich glaube, so langsam komme ich dahinter.
Mein Fehler war wohl, „schwierig“ mit „hohe Laufzeit“ zu interpretieren. Aber das SAT-Problem zeigt ja gerade, dass es so nicht ist.
Wenn ich es jetzt also richtig verstanden habe, dann ist die Wichtigkeit der NP-Vollständigkeit darin begründet, dass abhängig von der Aussage „P gleich NP“ man über viele Probleme generell etwas aussagen kann. Wenn P gleich NP gilt (was ja wohl eher unwahrscheinlich ist), dann könnte man über den Umweg SAT (zum Beispiel) alle NP-Probleme in polynomialer Zeit auf einer DTM lösen.Wenn P ungleich NP, dann müsste man gar nicht erst nach Lösungen in polynomialer Zeit suchen, da sie für NP-Probleme auf einer DTM nicht existieren. Habe ich das jetzt richtig verstanden?

Torsten

#6

Wenn P ungleich NP, dann müsste man gar
nicht erst nach Lösungen in polynomialer Zeit suchen, da sie
für NP-Probleme auf einer DTM nicht existieren. Habe ich das
jetzt richtig verstanden?

Ja,
zumindest für die Gesamtheit aller NP Probleme wäre das
nicht möglich.

Gruss
Enno