Blatt8

[kukugo]

Habt jemand ein Idee ,wie man Aufgabe 2.1 loesuen kann?

[Johann]

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:

• Der Graph muss zusammehängend sein
• Kein Knoten darf einen ungeraden Grad haben

Punkt 1 lässt sich mit Tief- oder Breitensuche lösen, wobei beide eine worst-case Laufzeit von |V| + |E| haben. Punkt 2 hab ich einfach ganz simpel so gemacht: Man geht alle Kanten durch und führt Buch über die Grade (Aufwand: |E|) und geht am Ende das "Buch" durch und schaut, ob auch alle Grade gerade sind (Aufwand: |V|). Das gibt einen Gesamtaufwand 2(|V|+|E|) und damit linear zur Eingabe und folglich in P.

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.

[colajunkie]

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...