Komplexitätstheorie Hausaufgaben 4

Hausaufgabe 4.1

Zeige, daß 2SAT in P liegt.

Hausaufgabe 4.2

Reduziere 3CNF auf INTEGER PROGRAMMING:

Gegeben: Ein System von linearen Ungleichungen in n Variablen mit natürlichen Zahlen als Koeffizienten.
Gefragt: Gibt es eine Lösung mit natürlichen Zahlen?

Beispiel:

Instanz 1: a >= 1, b >= 0, a+b <=3, 2b >= 3
Lösung: a=1, b=2

Instanz 2: a >= 1, b >= 0, a+b <=3, 2b >= 5
Keine Lösung!

Hausaufgabe 4.3

Zeige, daß INTEGER PROGRAMMING in NP liegt.

Hausaufgabe 4.4

Zeige, daß eine sonst polynomiell zeitbeschränkte TM M mit Eingabe x, die polynomiell oft eine Subroutine aufruft, die in |x| polynomiell zeitbeschränkt ist, insgesamt ebenfalls polynomiell zeitbeschränkt ist.

Zeige, daß eine sonst polynomiell zeitbeschränkte TM M' mit Eingabe x, die polynomiell oft die eben beschriebene TM M als Subroutine aufruft, exponentiell viel Zeit benötigen kann.