Komplexitätstheorie
- Formelspiel
- Folgerungsbeziehungsproblem der Prädikatenlogik
- Erfüllbarkeitsproblem der Prädikatenlogik
- Erfüllbarkeitsproblem der Aussagenlogik
- Polynomialzeitreduktion
- Log-Raum-Reduktion
- Reduktion
- Satz SUBSET-SUM is NP-vollständig
- Satz TQBF ist PSPACE-vollständig
- Erfüllbarkeitsproblem für quantifizierte boolesche Formeln
- Satz EQ-ROBP in BPP
- Satz NL teil von P
- Komplexitätsklasse
- Komplexitätstheorie
- Satz FORMULA-GAME ist PSPACE-vollständig
- Problem E gewinnt Formelspiel
- Gewinnstrategie
- Spiele
- Satz 3SAT ist NP-vollständig
- Satz 3SAT is poly reduzierbar auf CLIQUE
- nichtdeterministisch polynomielle Zeit
- LSPACE
- deterministisch polynomielle Zeit mit Orakel-TM
- Orakel-Turingmaschine
- Orakel
- Problem der Äquivalenz zweier Regulärer Ausdrücke mit Potenzierung
- Problem der Äquivalenz zweier Regulärer Ausdrücke
- EXPSPACE-Vollständigkeit
- PSPACE-Vollständigkeit
- PSPACE
- deterministisch polynomielle Zeit
- EXPTIME
- EXPSPACE
- Satz PSPACE Teilmenge von EXPTIME
- Raumhierarchiesatz
- Zeitkonstruierbare Funktion
- Hierarchiesätze
- Satz TQBF ist nicht NL
- Satz NL ist eine echte Teilmenge von PSPACE
- Raumkonstruierbare Funktion
- Satz coPATH is in NL
- Unerreichbarkeitsproblem in Graphen
- Erreichbarkeitsproblem in Graphen
- Satz PATH is NL-vollständig
- Satz PATH ist in P
- NLSPACE
- coNL
- coNP
- Satz Falls B in L und A log-raum reduzierbar auf B dann A in L
- Satz NP-vollständig durch Reduktion von NP-vollständig
- NL-Vollständigkeit
- NP-Schwer
- NL-Schwere
- Logarithmische Platzkomplexität berechenbare Funktion
- Satz von Savitch
- Satz 0^k1^k ist L
- Satz von Cook und Levin
- Problem der Äquivalenz zweier ROBP
- Cliquenproblem
- Satz RELPRIME ist in P
- Hamiltonkreisproblem
- Verstärkungslemma
- Zeitkomplexität
- Big O
- Teilsummenproblem
- SPACE
- small o
- Satz PSPACE gleich NPSPACE
- Satz P Teilmenge von PSPACE
- Satz NP gdw. NDTM
- Satz Laufzeit zusätzlicher Bänder
- Satz Hamiltonwegproblem ist in NP
- Satz Laufzeit Determinisierung von Nichtdeterminismus
- Satz Hamiltonwegproblem ist in EXPTIME
- Satz Falls B NP-vollständig und B in P dann P gleich NP
- Satz Falls SAT in P dann P gleich NP
- Satz CLIQUE is NP-vollständig
- RELPRIME
- Randomisierte polynomielle Zeit
- Polynomialzeit berechenbare Funktion
- Polynomialzeit
- Platzkomplexität
- Null-Fehler probabilistische polynomielle Zeit
- P versus NP
- NTIME
- NSPACE
- NP-Vollständigkeit
- nichtdeterministische Polynomialzeit
- Kürzeste Wegeproblem
- Landau-Symbole
- coRP
- 3SAT
- beschränkte Fehlerwahrscheinlichkeit probabilistische polynomielle Zeit
- 3-dimensional matching
- TIME
- Hamiltonwegproblem