Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
NP - Reduktionen
ich weiss, es gibt dafuer kein Kochrezept, aber wie kann man denn SUMMIERT auf CLIQUE reduzieren (siehe Braindump SS 2012) ?
ein kleiner Anhaltspunkt wuerde mir schon reichen…
diese Reduktionen mit SAT usw haben es echt in sich!!
Danke!
Anhaltspunkt: Die Lösungsidee ist die gleiche wie zu Aufgabe 29 auf Blatt 5.
MfG
Rolf Wanka
1 Like
Ich sitze jetzt auch schon einige Zeig über der Reduktion und wollte deswegen noch 2 Dinge nachfragen:
-
Zur Aufgabe 29 (Blatt 5)
Als “Muster”-Lösung hatte ich,
L={w#w|w \in {0,1}*} <= H_epsilon<M>, falls x \in L
f(x)={
0, sonst
Für M: (1) Hält
(Kann mir jemand bestätigen ob meine Lösung so stimmt?)
- Inwiefern hilft mir das bei der polynomiellen Reduktion, dort muss ich ja gar keine TM angeben?
Die Lösung dürfte so stimmen.
Zum zweiten Punkt: In einer Reduktion gibts zwei Orte, wo etwas “geschehen” kann, zum einen in f und zum anderen, in dem was f generiert.
Bei Aufgabe 29 hat man praktisch die gesamte Arbeit in f erledigt, weil man es ausnahmsweise darf (-> “warum?” ist wichtig). Ohne die Aufgabe aus der Klausur auch nur ansatzweise zu kennen: Wenn die Lösungsidee ähnlich ist, dann wird die Funktion f wieder eine tragende Rolle spielen.
Ich hab das jetzt mal so gedacht (für Braindump 09):
a)
<G,3> falls x Element UNSORTIERT
f(x)={
<G,4> falls x kein Element UNSORTIERT
wobei ich als G einen Graph angegeben hab, der nur 3 Knoten hat, und diese alle miteinander verbunden sind.
Die Laufzeit von f ist polynomiell, da UNSORTIERT in P liegt (Weil ich muss ja nur n-1 Vergleiche durchführen).
Also hat dann auch f polynomielle Laufzeit.
Also gilt x Element UNSORTIERt <=> f(x) Element CLIQUE
Das ist jetzt sehr kurzgefasst, aber würde des so vom Prinzip her gehen?
b)
Hier kann ich doch einfach sagen, dass auch CLIQUE jetzt in polynomieller Zeil entscheindbar ist.
0#1 falls x Element CLIQUE
f(x)={
1#0 falls x kein Element CLIQUE
und dann weiß ich nach gleichen Argumentationen wie oben von der Laufzeit, x Element CLIQUE <=> f(x) Element UNSORTIERT gilt.
Auch alles nur sehr knapp gefasst hier.
Meinungen dazu?
Hat keiner einen Meinung, ob das so geht oder nicht?
Ich hab eine Frage zur Altklausur 2011, Aufgabe 6c)
Und zwar ist die Frage, ob unter der Annahme P ≠ NP, SUM NP-vollständig ist (SUM ist “binärePartialsumme”, und im Braindump nicht näher definiert).
Ich hab im entsprechenden Abschnitt im Skript nachgelesen (2.11, 2.12), finde aber keine Begründung, für ja oder nein.
Für NP-Vollständigkeit:
- SUM ∈ NP
- SUM ist NP-schwer
Ich geh davon aus, dass SUM ∈ P gilt, also auch SUM ∈ NP (da P ⊆ NP), Punkt 1 wäre also erfüllt.
Aber ob SUM NP-schwer ist, dafür müsste ich ja zeigen, dass ich alle Sprachen auf SUM reduzieren kann, und das kann ich so ohne weiteres nicht beweisen… oder?
Hat einer ne Idee?
Versuch es doch mal auf eine andere Weise:
P ≠ NP, SUM ∈ P (laut dir)
Was wäre denn die Folge, würde sich SUM als NP-complete erweisen?
Ohne die Aufgabe jetzt angeschaut zu haben: Das beweist man in der Regel damit, indem man eine bereits NP-vollständige Sprache auf SUM reduziert, weil die polynomielle Reduktion transitiv ist.
Wenn diese dann auf SUM reduzierbar ist, sind also auch alle anderen auf SUM reduzierbar, weil bereits gezeigt wurde, dass sie auf die andere NP-vollständige Sprache reduzierbar sind.
In der Vorlesung haben wir immer SAT als NP-vollständige Sprache reduziert.
Wenn SUM NP-vollständig:
SUM ∈ P <=> P = NP
Sprich: Wäre SUM NP-vollständig, dann wäre P = NP, was der Annahme widerspricht. Also kann SUM nicht NP-vollständig sein (falls SUM ∈ P).
Na gut, hört sich richtig an. 
Ja, das meinte ich mit „so ohne weiteres“, die Aufgabe beantworten, ohne das Herumreduzieren anzufangen. 
Hey 
kurze Frage :
warum hast du hier :
eine Clique mit 3 konten fuer x Element Unsortiert und eine Clique mit 4 Knoten fuer x kein Element Unsortiert ??
und Danke
ICh hab mir einmal ein Element genommen, das in CLIQUE liegt und einmal ein Element, das nicht in CLIQUE liegt. Dafür hab ich willkürlich einen Graphen genommen, der einfach nur eine CLIQUE der Größe 3 aber keine der Größe 4 hat. Weil ich will ja bei der Reduktion x Element UNSORTIERT <=> f(x) Element CLIQUE. Hilft dir das weiter?
Eigentlich was ich nicht ganz verstanden hab ist warum hast du die beide Zahlen 3 und 4 genommen ??
Warum nicht 5 und 6 zum Beispiel
… er hat vermutlich auf sein Blatt ein konkretes G gemalt für das 3 und 4 Sinn ergibt … wenn nicht, dann komisch 
ja so hab ich das gemacht… was hättet ihr denn an dieser stelle gemacht?
Kannst du mir dann sagen wie hast du dein G skizziert ?
vllt eine Photo wenn es möglich 
und Danke !
Btw: Wir saßen an der Aufgabe heute über 2 Stunden, haben detailiert einen Algorithmus angegeben der Unsortiert auf CLIQUE reduziert (in O(n)) und das noch genau beschrieben (und uns natürlich gefragt, wie man das in der Klausur bitte hinkriegen soll). Dann schauen wir ins Forum und ??? löst das mit dem \in P Trick in ein paar Zeilen ^^
PS: Weiß denn jemand sicher, dass ???'s Lösung ausreicht in der Klausur? Oder sollte man da evtl noch den Algorithmus angeben, der UNSORTIERT entscheidet (rwanka, maybe? 
)
An der Stelle reicht irgendein <G,k> in CLIQUE, also z.B. auch ein einzelner Knoten und k = 1…