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.
Altklausur WS12/13
Hi,
wir sitzen an der Aufgabe 6b der Altklausur WS12/13 und wollten fragen, ob man fuer die Loesung folgendermaßen argumentieren kann.
Da man zeigen soll, dass ENDERIESIG mit Polynomzeitreduktion auf SAT reduzierbar ist, haetten wir gesagt, da man ja weiß, dass SAT NP-vollstaendig ist, also somit auch NP-schwer, dass ENDERIESIG in NP liegen muss, da sonst SAT nicht NP-schwer waere (NP-Schwere: L ist NP-schwer, wenn alle L’ element NP sich auf L reduzieren lassen). Kann man dies folgern, oder darf man das nicht, da man ja erst zeigen soll, dass ENDERIESIG <=p SAT gilt.
Gruesse,
kawa_blue
ENDERIESIG liegt in P. Damit lässt sich in polynomialzeit entscheiden ob x in ER liegt oder nicht.
Sorry, das beantwortet unsere Frage nicht wirklich. Klar kann man sagen, dass ENDERIESIG in P liegt, weil man entscheiden kann, ob es diese Form hat, allerdings wollten wir wissen, ob man durch die Annahme, dass ENDERIESIG <=p SAT gilt, ob man schlussfolgern kann, dass ENDERIESIG in NP ist (Begruendung siehe erster Post).
Das ER in NP liegt kannst du einfach so behaupten. P ist Teilmenge von NP bzw. laut Aufgabenstellung P=NP.
Man darf das glaube ich aber nicht mit eurer Argumentation machen, da ihr dabei die Richtung der Reduktion vertauscht.
Hey,
wir sitzen gerade auch vor dem Problem und wollten fragen, was ihr letztendlich als Loesung herausgebracht habt.
z.Z.: x ∈ ENDERIESIG ≤ SAT
f(x) = falls x ∈ ER,
0 falls x ∉ ER
ER ist in polynomialzeit entscheidbar. f ist total berechenbar => Reduktion in polynomialzeit.
x ∈ ER => f(x) ∈ SAT
x ∉ ER => f(x) ∉ SAT
Mehr sollte es nicht sein. Die Reduktionsfunktion haben wir uns so vom Manuel Schmitt erklären lassen. Wir dachten auch das muss viel komplizierter sein 
Super, vielen Dank! Habt ihr Lust eure komplette Lösung von der Klausur hier hochzuladen, damit man vergleichen kann?
Da man ja zeigen soll, dass ER <=p SAT gilt und man weiß, dass alle Sprachen aus NP auf SAT reduzieren kann (Satz von Cook), wird ER wohl in NP sein. Ob das tatsächlich auch in P ist (und dadurch auch in NP, da P Teilmenge von NP), ist für die Aufgabenstellung egal, oder (hier ist ja noch nicht P=NP) ?
Ist die KNF denn unabhängig von der Eigenschaft von ER ? Also könnte man einfach x1 und x2 zurückgeben falls x element ER ?
Was mir noch Kopfzerbrechen bereitet ist, wenn die nächste Aufgabe, also bei der Annahme, dass P=NP: Wenn man das nicht annimmt, also P immer noch eine Teilmenge von NP ist, wo geht die Reduktion genau kaputt ? Wahrscheinlich bei der Laufzeit der Reduktionsfunktion, weil sie dann nicht polynomiell ist, warum kann ich mir aber nicht genau erschließen. Hat da jemand eine gute Erklärung ?
Wenn du den Satz von Cook verwendest (besser gesagt Teil (ii) unseres Beweises dessen), dann müsstest du „nur“ zeigen, dass ER in NP.
Allerdings ist ER in P und anscheinend so trivial, dass das in der Lösung oben nicht mal näher erklärt wird. Ich hätte einen Algorithmus angegeben, also z.B. „Alle bis zum vorletzten Element aufsummieren und das mit dem letzten vergleichen“ => Laufzeit O(n)
Wenn x in ER ist, muss die Rückgabe in SAT sein. x1 und x2 sind nicht unbedingt erfüllbar. wie im Lösungsvorschlag oben aber schon. Immer x ∈ ER <=> f(x) ∈ SAT beachten!
Was meinst du mit Kaputtgehen der Reduktionsfunktion?
Ich denke folgendes ist korrekt (vielleicht etwas knapp): Wenn P = NP, kann man SAT (und damit alle NP vollständigen Probleme) in Polynomialzeit auf ER reduzieren, wodurch ER NP-schwer wird und damit NP-vollständig.
Ist auch so 
Wie kommt man denn drauf, das man SAT auf ER reduzieren kann? Da steh ich auf dem Schlauch, die anderen Schritte sind klar 
Wenn P=NP gilt kann man SAT in polynomialzeit entscheiden.
f(x) = <5,3,2> , falls x ∈ SAT
0 , sonst
x ∈ SAT => f(x) ∈ ER
x ∉ SAT => f(x) ∉ ER
Damit hast du die NP-schwere. Für NP-Vollständig muss ER noch in NP liegen: ER ∈ P <=> ER ∈ NP
Hoffe das ist richtig und hilft weiter
Klar, danke dir
necro,
Warum denn <5,3,2> du hast dann da doch (a_1+…+a_n-1) < a_n nicht erfuellt oder? Warum wuerdest du das machen und nicht z.b. <bin(1)#bin(2)#bin(50)>?