UNItopia News: Brett Computer, Gruppe Allgemeines, Artikel 1742

-------------------------------------------------------------------------------
Titel: Beweis NP-Vollstaendigkeit (fuer Masochisten)
Artikel: 1742                                          Bezug: 1739
Verfasser: Tao                                         Datum: 04.03.05 11:52:59
-------------------------------------------------------------------------------
Fuer alle,  die es interessiert, kann man  die NP-Vollstaendigkeit von
diesem Problem  auch beweisen.  Das  zu verstehen ist  allerdings ohne
Vorkenntnisse nicht moeglich.

Das Serrin-Problem:

Gegeben:  Eine Menge  M endlich  vieler natuerlicher  Zahlen,  und die
natuerlichen Zahlen X und E.

Gesucht: Eine Teilmenge T von  M, deren Elemente aufsummiert die Summe
S ergeben. Fuer S muss gelten: S>=X und S<=X+E.


1) Das Serrin-Problem liegt in NP
Eine Loesung (die Teilmenge  T) wird nichtdeterministisch geraten, und
in Polynomialzeit ueberprueft, ob die Bedingungen fuer S gelten.

2) Das Serrin-Problem ist NP-hart
Das  Rucksackproblem   (aus  einer  Menge   natuerlicher  Zahlen  eine
Teilmenge suchen, sodass ihre Summe S eine gegebene natuerliche Zahl N
nicht   uebersteigt,   und  S   maximal   ist)  ist   bewiesenermassen
NP-vollstaendig.

Man kann  nun eine Instanz  des Rucksackproblems in  Polynomialzeit in
eine  Instanz  des  Serrin-Problems  verwandeln. Dazu  setzt  man  die
Variablen aus dem Serrin-Problem folgendermassen: X=0 und E=N.

Das Rucksack-Problem laesst sich auf das Serrin-Problem reduzieren.
=> Das Serrin-Problem ist NP-hart.

Das Serrin-Problem ist in NP enthalten und NP-hart
=> Das Serrin-Problem ist NP-vollstaendig.

qed.


Die  Reduktion hat die  folgende Idee:  Wenn man  ein bewiesenermassen
schweres   Problem  in   ein   zweites  umwandeln   kann,  und   diese
Problemloesung liefert auch eine  Loesung fuer das erste Problem, dann
ist das erste Problem nicht schwerer zu loesen als das zweite.

Beispiel:
1. Problem: Die Summe von zwei Zahlen A, B berechnen
2. Problem: Die Summe von drei Zahlen A, B, C berechnen

Das erste  Problem kann ich auf  das zweite reduzieren,  indem ich C=0
setze. Also ist das zweite Problem mindestens so schwer wie das erste.


Falls  sich jemand  wider  Erwarten fuer  sowas  begeistern kann,  dem
empfehle   ich  "Theoretische  Informatik   -  kurzgefasst"   von  Uwe
Schoening,  oder "Theoretische  Informatik  - ein  algorithmenbasierte
Einfuehrung" von Ingo Wegener.

Gruss,
Tao