Komplexität

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

  • P
    • Deterministische TM
    • Maximal Polinomielle Zeit
  • NP
    • Nicht deterministische TM
    • Maximal Polinomielle Zeit im optimalen Durchlauf

Zuweisung

Uniformes Kostenmaß

1

Logarithmisches Kostenmaß

Anzahl der zu ändernden Bits ($log_2(n)$)

Polinomielle Reduzierbarkeit

Wie „normale“ Reduzierbarkeit. Nur muss zusätzlich f polynomielle Komplexität haben.

$A \le_P B$

Folgerung

  • $B \in P \Rightarrow A \in P$
  • $B \in NP \Rightarrow A \in NP$

NP-Hart

A ist NP-Hart, wenn gilt:

  • $\forall L \in NP : L \le_P A$

Heuristisch lösen

NP-Vollständig

A ist NP-Vollständig, wenn gilt:

  • $\forall L \in NP : L \le_P A$
  • $A \in NP$
users/skruppy/ext/uni/4/fsk/komplexitaet.txt · Zuletzt geändert: 2013/07/28 21:12 von skruppy