Thread fehlte bisher noch 
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.
Thread fehlte bisher noch
Probeklausur, Aufgabe 4
Hallo,
kann man das einfacher machen als mit einer reduktion auf PATH? (n^2 * n^2 adjazenzmatrix basteln, wo der pfad von start zum ziel einmal den kompletten originalgraphen abläuft, also pfade (1->->2), (2->->3), … zu suchen?
oder darf man einfach PATH mehrfach aufrufen?
Mein momentan größtes Problem mit der Aufgabe ist, dass laut https://de.wikipedia.org/wiki/Erreichbarkeitsproblem_in_Graphen SCONN und PATH ein und das selbe sind. Wie finde ich denn raus was der Lehrstuhl mit einem bestimmten Kürzel meint?
Das ist nicht das Gleiche.
PATH ist das Problem, das für zwei gegebene Knoten s, t in einem Graph sagt, ob es einen (beliebig langen) Pfad von s nach t gibt.
Dahingegen ist SCONN das Problem, dass alle Knoten betrachtet und prüft, ob es von jedem Knoten aus einen (beliebig langen) Pfad zu jedem anderen Knoten gibt.
1 „Gefällt mir“
Ok, da hätte ich genauer lesen müssen.
Aber ich bin imme noch verwirrt. Löst man mit 2. nicht auch automatisch 1. und 3.?
Hm. 1. und 2. sind alles, was du für 3. brauchst.
Ist dann der Unterschied zwischen 1. und 2., nur dass man zeigt, dass die Reduktion logspace ist? Oder soll man das bei der 1. irgendwie anders zeigen, ohne Reduktion?
Bei der 1 gibst du eine TM an, die nichtdeterministisch ist und logarithmischen Platzverbrauch hat, die SCONN löst.
Bei der 2 machst du die Reduktion
Bei der 3 folgerst du aus 1 und 2, dass SCONN NL-vollständig ist.
Ach so, könnte ich 1. auch lösen indem ich SCONN auf PATH reduziere?
Wenn ich jetzt nicht ganz falsch liege, dann nein.
Wenn man X-Vollständigkeit zeigen will, dann muss man ja auch zeigen, dass Problem P (1) elem. X und (2) X-schwer ist. Wenn deine Aussage stimmen würde, könnte man sich den ersten Schritt ja sparen.
Ich glaube eher, dass gemeint ist, dass man die 1. lösen könnte, indem man SCONN <= PATH zeigt (also genau die Reduktion in die andere Richtung als in 2.), jedenfalls würde ich das so auch aus der 3. Aufgabe des 10. Aufgabenblattes herauslesen. Allerdings weiß ich nicht, ob das tatsächlich Sinn machen würde.
SCONN <= PATH heisst ja “SCONN ist höchstens so schwirig wie PATH”. Dementsprechend müsste man damit schon Klassenzugehörigkeit zeigen können. Ich weiss allerdings nicht genau wie man schwere zeigt.
Das machst du in der 2., indem du durch reduktion von path zeigst, dass es schwer genug ist, dass es auch path, also das „urproblem“ von NL löst.
Ach stimmt, dann muss Reduktion einmal so rum und einmal anders herum doch eine legitime Lösung sein.
Ich meine, ich habe die Aufgabe a) damals gelöst, indem ich einfach PATH als Unterprogramm (da PATH in NL) auf alle möglichen Knotenkombinationen aufgerufen habe (ganz sicher bin ich mir nicht mehr, und kann es wegen nicht abgeholten Blatt auch nicht überprüfen). Jedenfalls habe ich darauf aber volle Punktzahl bekommen.
Was meint ihr, würde das in der Klausur auch durchgehen? Erscheint mir etwas zu einfach.
Edit: Anstatt einem Unterprogrammaufruf könnte man auch einfach den (leicht angepassten) Code von PATH_NL aus der Vorlesung an die Stelle schreiben. Das müsste dann eigentlich klappen.