Liste von Sätzen der Informatik – Wikipedia
aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
- 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 Immerman und Szelepcsényi: Die Komplexitätsklasse NL ist unter Komplementbildung abgeschlossen.
- Satz von Ladner: Falls
gilt, gibt es Probleme, die weder NP-vollständig sind noch in P liegen.
- 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.