This group gathers theorems of computability theory and computational complexity theory, which ask what can be computed at all and how many resources the computation needs. It covers undecidable problems, the recursion and degree theory of computable functions, the classes of problems solvable in bounded time or space, results on completeness and hierarchies, and the theory of formal languages. A theorem belongs here when its cited article places it in computability theory, computational complexity or formal language theory.
Browse By
Computability and Complexity Theory
Filter Results24 entries
Sources
Entscheidungsproblem (Wikipedia)
Has Member: Church's Theorem, Lead section
Such an algorithm was proven to be impossible by Alonzo Church and Alan Turing in 1936.
Has Member: Entscheidungsproblem, Lead section
computer science, the Entscheidungsproblem (German for 'decision problem'; pronounced [ɛntˈʃaɪ̯dʊŋspʁoˌbleːm]) is a challenge
View the SourceRice's theorem (Wikipedia)
Wikimedia FoundationHas Member: Rice's Theorem, Lead sectionQuote, Has Member: Rice's Theorem, Lead section
In computability theory, Rice's theorem states that all non-trivial semantic
Cook-Levin Theorem (Wikipedia)
Wikimedia FoundationHas Member: Cook-Levin Theorem, Lead sectionQuote, Has Member: Cook-Levin Theorem, Lead section
In computational complexity theory, the Cook-Levin theorem, also known as
Kleene's Recursion Theorem (Wikipedia)
Wikimedia FoundationHas Member: Kleene's Recursion Theorem, Lead sectionQuote, Has Member: Kleene's Recursion Theorem, Lead section
In computability theory, Kleene's recursion theorems are a pair of fundamental
Post's theorem, Wikipedia
Has Member: Post's Theorem, Lead sectionQuote, Has Member: Post's Theorem, Lead section
In computability theory, Post's theorem, named after Emil Post, describes
Myhill-Nerode theorem (Wikipedia)
Has Member: Myhill-Nerode Theorem, Lead sectionQuote, Has Member: Myhill-Nerode Theorem, Lead section
In the theory of formal languages, the Myhill-Nerode theorem provides a necessary
Time hierarchy theorem (Wikipedia)
Has Member: Time Hierarchy Theorem, Lead sectionQuote, Has Member: Time Hierarchy Theorem, Lead section
In computational complexity theory, the time hierarchy theorems are important
Savitch's theorem, Wikipedia
Has Member: Savitch's Theorem, Lead sectionQuote, Has Member: Savitch's Theorem, Lead section
In computational complexity theory, Savitch's theorem, proved by Walter Savitch
Space hierarchy theorem, Wikipedia
Has Member: Space Hierarchy Theorem, Lead sectionQuote, Has Member: Space Hierarchy Theorem, Lead section
In computational complexity theory, the space hierarchy theorems are separation
Immerman-Szelepcsenyi theorem, Wikipedia
Has Member: Immerman-Szelepcsenyi Theorem, Lead sectionQuote, Has Member: Immerman-Szelepcsenyi Theorem, Lead section
In computational complexity theory, the Immerman-Szelepcsényi theorem states
NP-intermediate (Wikipedia)
Has Member: Ladner's Theorem, Lead sectionQuote, Has Member: Ladner's Theorem, Lead section
In computational complexity, problems that are in the complexity class NP
Blum's speedup theorem, Wikipedia
Has Member: Blum's Speedup Theorem, Lead sectionQuote, Has Member: Blum's Speedup Theorem, Lead section
In computational complexity theory, Blum's speedup theorem, first stated
Wikipedia: Smn theorem
WikipediaHas Member: S-m-n Theorem, Lead sectionQuote, Has Member: S-m-n Theorem, Lead section
In computability theory the S mn theorem, written also as "smn-theorem"
Sipser-Lautemann theorem, Wikipedia
Has Member: Sipser-Lautemann Theorem, Lead sectionQuote, Has Member: Sipser-Lautemann Theorem, Lead section
In computational complexity theory, the Sipser-Lautemann theorem or Sipser-Gács-Lautemann
Toda's theorem, Wikipedia
Has Member: Toda's Theorem, Lead sectionQuote, Has Member: Toda's Theorem, Lead section
Toda's theorem is a result in computational complexity theory that was proven by Seinosuke Toda in his
Valiant-Vazirani theorem, Wikipedia
Has Member: Valiant-Vazirani Theorem, Lead sectionQuote, Has Member: Valiant-Vazirani Theorem, Lead section
The Valiant-Vazirani theorem is a theorem in computational complexity theory stating that if there is a polynomial
PCP theorem, Wikipedia
Has Member: PCP Theorem, Lead sectionQuote, Has Member: PCP Theorem, Lead section
In computational complexity theory, the PCP theorem (also known as the PCP
Rice-Shapiro theorem, Wikipedia
Has Member: Rice-Shapiro Theorem, Lead sectionQuote, Has Member: Rice-Shapiro Theorem, Lead section
In computability theory, the Rice-Shapiro theorem is a generalization
Myhill isomorphism theorem, Wikipedia
Has Member: Myhill Isomorphism Theorem, Lead sectionQuote, Has Member: Myhill Isomorphism Theorem, Lead section
In computability theory the Myhill isomorphism theorem, named after John
Friedberg-Muchnik theorem, Wikipedia
Has Member: Friedberg-Muchnik Theorem, Lead sectionQuote, Has Member: Friedberg-Muchnik Theorem, Lead section
logic, the Friedberg-Muchnik theorem is a theorem about Turing reductions that was proven independently by Albert
Greibach's theorem, Wikipedia
Has Member: Greibach's Theorem, Lead sectionQuote, Has Member: Greibach's Theorem, Lead section
In theoretical computer science, in particular in formal language theory, Greibach's theorem states that certain
Turing's proof - Wikipedia
Has Member: Turing's Proof, Lead sectionQuote, Has Member: Turing's Proof, Lead section
more technically, that some decision problems are "undecidable" in the sense that there is no single algorithm
Richardson's theorem (Wikipedia)
Has Member: Richardson's Theorem, Lead sectionQuote, Has Member: Richardson's Theorem, Lead section
In mathematics, Richardson's theorem establishes the undecidability of the equality of real numbers defined
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.