f: Größe der Eingabe → Anzahl der Rechenschritte
Meistens genügt f in O-Notation
TIME: Anzahl x der Rechenschritt → Menge an DTM die nach maximal x Rechenschritten terminieren.
TIME($1$) | Konstant | P | LOOP |
TIME($\log(n)$) | Logarithmisch | P | LOOP |
TIME($n$) | Linear | P | LOOP |
TIME($n\log(n)$) | P | LOOP | |
TIME($n^2$) | Quadratisch | P | LOOP |
TIME($n^3$) | Kubisch | P | LOOP |
TIME($2^n$) | Exponenziell | LOOP | |
TIME($n!$) | Faktoriell |
$2^{2^2}$ und das n-Mal ist auch in LOOP, aber nicht in P.
Menge entscheidbar ⇐ charakteristische funktion berechenbar
1
Anzahl der zu ändernden Bits ($log_2(n)$)
Wie „normale“ Reduzierbarkeit. Nur muss zusätzlich f polynomielle Komplexität haben.
$A \le_P B$
Folgerung
A ist NP-Hart, wenn gilt:
Heuristisch lösen
A ist NP-Vollständig, wenn gilt: