Blatt8
Re: Blatt8
Nein, noch nicht, aber ich möchte hier meinen Ansatz für die erste Aufgabe einfach mal bereitstellen
Das EC-Problem nennt sich Eulerkreisproblem. Um zu zeigen, dass EC in P ist, genügt es einen Algorithmus zu finden und diesen zu analysieren. Ein Eulerkreis hat dabei zwei Eigenschaften:
Vielleicht mag ja jetzt jemand Ansätze zur 2 rausrücken
Edit:
Huch, ich glaube die 2.1 ist gar nicht so kniffelig. Wenn L in NP ist, heißt das, es gibt eine nichtdeterministsche Turingmaschine, die L in O(t(n)) entscheidet. Wir haben ja gelernt, dass man jede NTM in eine DTM umwandeln kann, und ich vermute mal beim Aufwand für die Umwandlung kommt jetzt das ominöse Polynom p(n) irgendwo ins Spiel. Oder so.
Edit2:
Jep, sieht gut aus: http://www4.informatik.tu-muenchen.de/l ... andout.pdf (Strg+F "umwandeln"). Eine polynomielle NTM lässt sich in eine exponentiell beschränkte DTM umwandeln mit Aufwand O(c^p(n)). Passt.
Das EC-Problem nennt sich Eulerkreisproblem. Um zu zeigen, dass EC in P ist, genügt es einen Algorithmus zu finden und diesen zu analysieren. Ein Eulerkreis hat dabei zwei Eigenschaften:
- Der Graph muss zusammehängend sein
- Kein Knoten darf einen ungeraden Grad haben
Vielleicht mag ja jetzt jemand Ansätze zur 2 rausrücken
Edit:
Huch, ich glaube die 2.1 ist gar nicht so kniffelig. Wenn L in NP ist, heißt das, es gibt eine nichtdeterministsche Turingmaschine, die L in O(t(n)) entscheidet. Wir haben ja gelernt, dass man jede NTM in eine DTM umwandeln kann, und ich vermute mal beim Aufwand für die Umwandlung kommt jetzt das ominöse Polynom p(n) irgendwo ins Spiel. Oder so.
Edit2:
Jep, sieht gut aus: http://www4.informatik.tu-muenchen.de/l ... andout.pdf (Strg+F "umwandeln"). Eine polynomielle NTM lässt sich in eine exponentiell beschränkte DTM umwandeln mit Aufwand O(c^p(n)). Passt.
338364: <Alanna> Saying that Java is nice because it works on all OS's is like saying that anal sex is nice because it works on all genders
-
- Beiträge: 36
- Registriert: Mi 5. Nov 2008, 14:52
- Wohnort: Wie viel Minuten zum HSaF? Einmal über die Straße...
Re: Blatt8
Im Sipser steht auch was dazu (unter Beachtung der Definition 7.12, dass P die ein-band-TMs meint) steht das mehr oder weniger in 7.11...