Die Klasse NN

• Gegeben: Problem P, P ∈ NN

• Löse P mit Turingmaschine M:

  • M ist nichtdeterministische Maschine
  • Rate nichtdeterministisch Lösung
  • Schreibe Lösung auf Band
  • Lese Eingabe von Band

• ⇒ Laufzeit von M ist < 0 (nach Definition)

Notizen: