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.

F

• 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.

H

• 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.

I

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

M

• 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.)

N

• No-Free-Lunch-Theoreme: Alle Suchalgorithmen sind im Durchschnitt gleich gut.
• Nyquist-Shannon-Abtasttheorem: Ein kontinuierliches, bandbegrenztes Signal mit einer Minimalfrequenz von 0 Hz und einer Maximalfrequenz $f_{max}$ muss mit einer Frequenz von mindestens $2\cdot f_{max}$ abgetastet werden, damit man aus dem zeitdiskreten Signal das Ursprungssignal ohne Informationsverlust rekonstruieren kann.

P

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

R

• 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 gibt kein allgemeines Verfahren, das für jeden Algorithmus feststellen kann, ob die von ihm beschriebene Funktion eine gewünschte Eigenschaft hat.

S

• 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.

Siehe auch

• Liste bedeutender Personen für die Informatik