die Klassen P und NP

Für Pol = Menge der Polynome:

• P = DTIME(Pol)

  Sprachen (Probleme) mit effizienten Algorithmen

• NP = NTIME(Pol)

  enthält schwierige Sprachen (Probleme)

Es gibt noch schwere Probleme (,,oberhalb von NP``)

Das Programm einer nichtdeterministischen Maschine kann man sich so vorstellen: 1. raten, 2. verifizieren. Für NP-Maschinen enthlten 1. und 2. nur polynomiell viele Schritte...

für ein vorher feststehendes Polynom (insbesondere darf es nicht von der Eingabe abhängen).

Es gilt DTIME(f ) $\subseteq$ NTIME(f ) $\subseteq$ NSPACE(f )

(in f (| w|) Zeit kann auch nur f (| w|) Platz verbraucht werden)