Muirauqa's Brain

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.

====== Komplexität ======
''f'': Größe der Eingabe -> Anzahl der Rechenschritte \\
Meistens genügt ''f'' in O-Notation

''TIME'': Anzahl ''x'' der Rechenschritt -> //Menge// an //D//TM 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