Automaten
Diese Menge enthält alle Wörter, die ein EA M akzeptiert.
L(M)
So viele Bänder hat eine 1-Band Turingmaschine
2 Bänder (Eingabe- und Arbeitsband)
Diese Komplexitätsklasse enthält alle in Polynomialzeit lösbaren Probleme
P
Diese Aussage wird von L1 <=_EE L2 impliziert.
L2 in L_RE => L1 in L_RE.
Mit dieser Konstruktion kann man L1 union L2 aus 2 EAs konstruieren.
Produktautomat.
Algorithmus.
Diese Klasse enthält alle in Polynomialzeit verifizierbare Probleme
NP
Bei einer EE-Reduktion muss die reduzierende TM M diese wichtige Eigenschaft immer erfüllen.
M muss immer halte (Bei R-Reduktionen nicht unbedingt).
Dieser Satz formalisiert die Idee, dass für lange Wörter mindestens ein Zustand im EA mehrmals besucht wird.
Pumping-Lemma
Church´sche These
Dieses Statement würde die polynomielle Umwandlung einer KNF in eine DNF Formel verhindern.
P ≠ NP
Diesen Trick benutzt man häufig bei Reduktionen, wie L_U <= L_empty
Die eigene Eingabe ignorieren und eine andere TM simulieren.
So viele verschiedene Suffixsprachen L_x = {y : xy in L} kann es von einer regulären Sprache geben.
Nur endlich viele.
(L_empty)^c ist hierin aber nicht L_empty
L_RE, also die Menge der erkennbaren Probleme.
Dieser Satz impliziert die Gleichheit von PSPACE = NPSPACE und beinhaltet ein (...)^2 Term
Komplementärgraph
Für L_k = {x1y : x in Sigma^*, y in Sigma^(k-1)} braucht ein EA M mit L(M) = L_k mindestens so viele Zustände.
2^k
So viele Nummerierungen von Turingmaschinen gibt es.
Überabzählbar unendlich viele.
Mit diesem Trick können wir eine zu A äquivalente TM B bauen, mit Space_B(n) <= Space_A(n) / 2 + 2
Vergrösserung des Arbeitsalphabets.
Für den Satz von Rice zeigt man in diesem Fall einer Fallunterscheidung L_H,lambda <=_EE L
Der Fall, in dem Kod(M_leer) in L liegt.