Komplexitätstheorie
- Komplexitätstheorie
- Verstärkungslemma
- Polynomialzeitreduktion
- Zeitkomplexität
- Erfüllbarkeitsproblem für quantifizierte boolesche Formeln
- Big O
- Teilsummenproblem
- SPACE
- small o
- Satz von Cook und Levin
- Satz von Savitch
- Satz SUBSET-SUM is NP-vollständig
- Satz STCON is NL-vollständig
- Satz STCON ist in P
- Satz RELPRIME ist in P
- Satz PSPACE Teilmenge von EXPTIME
- Satz PSPACE gleich NPSPACE
- Satz P Teilmenge von PSPACE
- Satz NP-vollständig durch Reduktion von NP-vollständig
- 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
- Satz EQ-ROBP in BPP
- Satz 3SAT ist NP-vollständig
- Satz 3SAT is poly reduzierbar auf CLIQUE
- RELPRIME
- Reduktion
- Randomisierte polynomielle Zeit
- PSPACE
- PSPACE-Vollständigkeit
- Problem der Äquivalenz zweier ROBP
- Polynomialzeit berechenbare Funktion
- Polynomialzeit
- Platzkomplexität
- Null-Fehler probabilistische polynomielle Zeit
- P versus NP
- NTIME
- NSPACE
- NP-Schwer
- NP-Vollständigkeit
- nichtdeterministische Polynomialzeit
- NL-Vollständigkeit
- nichtdeterministisch polynomielle Zeit
- Kürzeste Wegeproblem
- Landau-Symbole
- Komplexitätsklasse
- Erfüllbarkeitsproblem der Aussagenlogik
- coRP
- deterministisch polynomielle Zeit
- coNP
- Cliquenproblem
- 3SAT
- beschränkte Fehlerwahrscheinlichkeit probabilistische polynomielle Zeit
- 3-dimensional matching
- TIME
- Hamiltonwegproblem
- Hamiltonkreisproblem
- Erreichbarkeitsproblem in Graphen