NP Probleme

[b1zarRe]

Bekannte NP Probleme:
Knapsack, Cliquenproblem, SAT, Traveling Salesman sind ja bekanntlich(oder auch nicht :b) NP-vollständige Probleme... Wisst ihr wie man das begründen kann?

Ich würde sagen, dass man bei alle Varianten (im schlimmsten Fall) 2^n Kombinationen braucht, um das Ergebnis festzustellen und das halt exponentiell hoch ist. Habe ich das richtig verstanden???

Ps.: Hatte die letzten Wochen einige Fragen gepostet und werde demnächst als "Dankeschön" eine Zusammenfassung hier hochladen... vielleicht hilfts ja dem ein oder anderen

 

[Marco13]

Naja... so einfach ist es halt doch nicht... Oder nicht direkt. Dazu ist die Formulierung "man braucht... bis zu 2^n Kombinationen" zu schwammig. Was macht genau dieses "Brauchen" aus?

 

[XHelp]

Damit würdest du nur zeigen, dass in NP liegt. Du musst noch zeigen, dass es NP-Hart ist. Da bietet sich eine Reduktion von einem den oben genannten Probleme auf dein Untersuchungs-Problem

 

[b1zarRe]

Stimmt, müsste mit Reduktionsverfahren arbeiten... Wir hatten in der Vorlesung dazu ein Beispiel mit Hamilton Pfad und TSP und festgestellt das es NP Vollständig ist. Aber sowas wurde schon für die Klausur verneint... also will ich mich da erst einmal nicht zu sehr reinsteigern, sondern "reines" NP begründen:

Also bein Knapsack hat man ja n Dinge mit je einem Gewicht g und einem Nutzwert n und man schaut halt, wieviel Sachen mit einem maximalen Nutzwert man in die Tasche bekommt ohne das Maximalgewicht zu überschreiten, richtig? Ich würde nun behaupten, dass wenn man n Dinge hat, man bis zu 2^n Kombinationen ausprobieren müsste, um festzustellen, welches die beste Kombinationen ist.

Beispiel: 3 Dinge also 2^3 = 8. Ich habe folgende Kombinationsmöglichkeiten:
1. Ding a
2. Ding b
3. Ding c
4. Ding a und b
5. Ding a und c
6. Ding b und c
7. Ding A und b und c
8. garnichts???? <- oder was habe ich hier vergessen?!

Ist die Begründung so schlüssig? beim SAT Problem ist genau das gleiche mit einer Wahrheitstabelle... nur beim Cliquenproblem hatte ich mir irgendwie als Lösung n^2 - 2 oder so aufgeschrieben... aber wenn es das wäre, dann wäre es doch nicht ein NP Problem oder???

 

[XHelp]

Naja, P ist eine Teilmenge von NP, also alles was P lieg, liegt auch in NP. Bei den "liegt es in NP?" Sachen, reicht wirklich meistens (für die Klausur) aus zu sagen: "Ja, es liegt in NP, da man einen Algo aufstellen kann, der das Problem in Nichtpolynomieller Zeit löst, z.B. Backtracking" Und natürlich beschreiben WIE man da bei diesem Konkretem Problem vorgehen sollte.

P.S. Bei dem Ergebnis von der Clique... hm. sicher dass es nicht einfach nur die Anzahl der Kanten ist?

 

[b1zarRe]

Wenn ich ein Beispiel mache mit 4 Knoten a,b,c,d kommt bei mir folgendes raus:
a kennt c
a kennt d
a kennt b
b kennt c
b kennt d (a kennt b ja durch "a kennt b" schon)
d kennt c

Also 6 Ergebnisse in dem fall n+2

Wenn ich aber wirklich alle Überorüfungen aufschreibe(und denke das muss ich) dann komme ich auf:
a kennt b
a kennt c
a kennt d
b kennt a
b kennt c
b kennt d
c kennt a
c kennt b
c kennt d
d kennt a
d kennt b
d kennt c

also insgesamt 12.

Für n = 10 sollten es 90 Kombinationen sein
Für n = 100 sollten es 990 Kombinationen sein -> also ca n^2 oder warum vertue ich mich da???