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: