Liste von Sätzen der Informatik

C

Satz von Cook: Es existiert eine Teilmenge von NP, auf die sich alle Probleme aus NP polynomiell reduzieren lassen. Diese Teilmenge heißt NP-vollständig.
CAP-Theorem: In einem verteilten System ist es unmöglich, gleichzeitig die drei Eigenschaften Consistency (Konsistenz), Availability (Verfügbarkeit) und Partition Tolerance (Ausfalltoleranz) zu garantieren.

Satz von Friedberg und Muchnik: Es gibt rekursiv aufzählbare Turinggrade, die echt zwischen 0 (Grad der entscheidbaren Mengen) und 0’ (Grad der Halteprobleme) liegen.

Satz von Herbrand: Sei $F$ eine geschlossene Formel in Skolemform, dann ist $F$ genau dann unerfüllbar, wenn es eine endliche Teilmenge der Herbrand-Expansion $E(F)$ gibt, die – im aussagenlogischen Sinn – unerfüllbar ist.
Hierarchiesätze: Zeit- und Raumkomplexitätsklassen bilden jeweils eine Hierarchie, können also in eine echte Teilmengenbeziehung gesetzt werden. Es gilt: $\operatorname {DTIME} {\big (}f(n){\big )}\subsetneq \operatorname {DTIME} {\big (}f(n)\cdot \log ^{2}(f(n)){\big )}$ und $\operatorname {DSPACE} {\big (}f(n){\big )}\subsetneq \operatorname {DSPACE} {\big (}f(n)\cdot \log(f(n)){\big )}$ .

Satz von Immerman und Szelepcsényi: Die Komplexitätsklasse NL ist unter Komplementbildung abgeschlossen.

Satz von Ladner: Falls $\mathbf {P} \neq \mathbf {NP}$ gilt, gibt es Probleme, die weder NP-vollständig sind noch in P liegen.

Satz von Myhill: Eine Menge natürlicher Zahlen ist genau dann kreativ, wenn sie vollständig für die Klasse aller rekursiv aufzählbaren Mengen ist.
Isomorphiesatz von Myhill: Zwei Mengen natürlicher Zahlen sind genau dann rekursiv isomorph, wenn sie one-one-äquivalent sind.
Satz von Myhill-Nerode: Es existiert genau dann ein deterministischer endlicher Automat, der die formale Sprache $L$ akzeptiert, wenn der Index der zugehörigen Nerode-Relation endlich ist. (Unter dieser Bedingung ist $L$ also regulär.)

No-Free-Lunch-Theoreme: Es gibt keinen Suchalgorithmus, der für alle Probleme gleichermaßen der beste ist.
Nyquist-Shannon-Abtasttheorem: Ein kontinuierliches, bandbegrenztes Signal mit einer Minimalfrequenz von 0 Hz und einer Maximalfrequenz $f_{\text{max}}$ muss mit einer Frequenz größer als $2\cdot f_{\text{max}}$ abgetastet werden, damit aus dem zeitdiskreten Signal das Ursprungssignal ohne Informationsverlust rekonstruiert werden kann.

Das Pumping-Lemma: Eigenschaft bestimmter Klassen formaler Sprachen, geeignet um nachzuweisen, dass eine formale Sprache nicht regulär bzw. nicht kontextfrei ist.

Rekursionssatz (Fixpunktsatz von Kleene): Zu einem gegebenen Quelltext-Modifikationsprogramm lässt sich immer ein Quelltext finden, dem die Modifikation nichts ausmacht.
Satz von Rice: Es ist im Allgemeinen nicht möglich, für einen gegebenen Algorithmus irgendeinen Aspekt seines funktionalen Verhaltens algorithmisch nachzuweisen.

Satz von Savitch: Ein von einer nichtdeterministischen Turingmaschine mit einer bestimmten Platzkomplexität lösbares Problem ist auf einer deterministischen Turingmaschine mit einer quadratisch höheren Platzschranke lösbar. Daraus ergibt sich die Gleichheit von PSPACE und NPSPACE.
Satz von Shannon: Der Satz gibt eine Charakterisierung perfekt sicherer Verschlüsselungsverfahren.