Re^3: NP-vollständig

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