User:Xxfooln/Books/Complexity Heirarchy

This user book is a user-generated collection of Wikipedia articles that can be easily saved, rendered electronically, and ordered as a printed book. If you are the creator of this book and need help, see Help:Books (general tips) and WikiProject Wikipedia-Books (questions and assistance).

Edit this book: Book Creator · Wikitext

Order a printed copy from: PediaPress

[ About ] [ Advanced ] [ FAQ ] [ Feedback ] [ Help ] [ WikiProject ] [ Recent Changes ]

Complexity Heirarchy

Ch1: Complexity class; List of computability and complexity topics; List of complexity classes; 2-EXPTIME; AC (complexity); AC0; ACC0; ALL (complexity); APX; Arithmetical hierarchy; CC (complexity); Co-NP; Co-NP-complete; Co-RE; Co-RE-complete; DLOGTIME; DSPACE; DTIME; E (complexity); ELEMENTARY; ESPACE; Exponential hierarchy; EXPSPACE; EXPTIME; FL (complexity); FNP (complexity); FO (complexity); FP (complexity); FPT (complexity class); GapP; GI (complexity); GI-complete; L (complexity); L/poly; LH (complexity); LOGCFL; NC (complexity); NE (complexity); NEXPTIME; NL (complexity); NL-complete; Nonelementary problem; NP (complexity); NP-complete; NP-easy; NP-equivalent; NP-hard; NP-intermediate; NSPACE; NTIME; P (complexity); P/poly; P-complete; Parity P; PH (complexity); PLS (complexity); PolyL; Polynomial-time approximation scheme; PPA (complexity); PPAD (complexity); PPP (complexity); PR (complexity); Pseudo-polynomial time; PSPACE; PSPACE-complete; PSPACE-hard; Quasi-polynomial time
Ch2: R (complexity); Random-access Turing machine; RE (complexity); RE-complete; S2P (complexity); SC (complexity); Sharp-P; Sharp-P-complete; SL (complexity); SNP (complexity); Strongly NP-complete; SUBEXP; TC (complexity); TC0; TFNP; UP (complexity); W hierarchy; Weakly NP-complete; XP (complexity class); Approximation-preserving reduction; Berman–Hartmanis conjecture; Blum axioms; Compression theorem; Immerman–Szelepcsényi theorem; Low and high hierarchies; P versus NP problem; Polynomial hierarchy; Reduction (complexity); Resource bounded measure; Savitch's theorem; Sipser–Lautemann theorem; Space hierarchy theorem; Structural complexity theory; Time hierarchy theorem; Toda's theorem; Valiant–Vazirani theorem; Computational complexity theory; Configuration graph; Padding argument; Aanderaa–Karp–Rosenberg conjecture; Advice (complexity); Analysis of algorithms; Approximation algorithm; Asymptotic computational complexity; Averaging argument; Best, worst and average case; Boolean circuit; Certificate (complexity); Circuit complexity; Circuits over sets of natural numbers; Cobham's thesis; Combinatorial optimization; Combinatorial search; Communication complexity; Complement (complexity); Complete (complexity); Complexity index; The Complexity of Songs; Computable topology; Computation tree; Computational complexity of mathematical operations; Computational resource; Computational topology; Computationally bounded adversary; Computing the permanent; Constructible function; Context of computational complexity
Ch3: Decision tree model; Descriptive complexity theory; Dynamic problem (algorithms); Effective complexity; Electronic Colloquium on Computational Complexity; Existential theory of the reals; Folded Reed–Solomon code; Gadget (computer science); Generalized game; Generic-case complexity; Geometric complexity theory; Half-exponential function; Hardness of approximation; HO (complexity); Information-based complexity; Integer circuit; Interactive proof system; Introduction to the Theory of Computation; Iterative compression; Klee–Minty cube; L-notation; L-reduction; Leaf language; List decoding; Log-space computable function; Log-space reduction; Log-space transducer; Logical depth; Low (complexity); Many-one reduction; Natural proof; Non-constructive algorithm existence proofs; Nondeterministic algorithm; Parameterized complexity; Pebble game; Polynomial-time reduction; Proof (truth); Proof complexity; Proper complexity function; Propositional proof system; PTAS reduction; Quantum capacity; Quantum complexity theory; Quantum computing; Randomness extractor; Randomness merger; Semi-membership; Smoothed analysis; SO (complexity); Sparse language; Switching lemma; Symmetric Turing machine; Time complexity; Transcomputational problem; Transdichotomous model; Truth-table reduction; Turing reduction; Unary language; Unique games conjecture; Universal hashing; Yao's principle; Analytical hierarchy; Arithmetical set; Borel hierarchy; Difference hierarchy; Post's theorem; Projective hierarchy; Tarski–Kuratowski algorithm; Wadge hierarchy; Grzegorczyk hierarchy; Boolean hierarchy; Computability; Computability theory; List of undecidable problems; Ackermann function; Admissible numbering; Algorithm characterizations; Alpha recursion theory; Automatic group; Automatic semigroup; Bounded quantifier; Busy beaver; Chain rule for Kolmogorov complexity
Ch4: Church–Turing thesis; Church–Turing–Deutsch principle; Circuit satisfiability problem; Complete numbering; Computability logic; Computable analysis; Computable function; Computable isomorphism; Computable number; Computation; Computation in the limit; Computational theology; Course-of-values recursion; Craig's theorem; Creative and productive sets; Decision problem; Description number; Double recursion; Effective method; Effective Polish space; Entscheidungsproblem; Enumerator (computer science); Fast-growing hierarchy; Forcing (recursion theory); Friedberg numbering; Gödel numbering for sequences; Halting problem; Hardy hierarchy; High (computability); History of the Church–Turing thesis; Hyperarithmetical theory; Index set (recursion theory); K-trivial set; Kleene's recursion theorem; Kleene's T predicate; König's lemma; Kolmogorov complexity; Lambda calculus; LOOP (programming language); Low (computability); Low basis theorem; Martin measure; Maximal set; McCarthy Formalism; Μ operator; Μ-recursive function; Myhill isomorphism theorem; Normal form (abstract rewriting); Numbering (computability theory); Oracle machine; PA degree; Π01 class; Post correspondence problem; Primitive recursive function; Primitive recursive functional; Primitive recursive set function; Recursion (computer science); Recursive language; Recursive ordinal; Recursive set; Recursively enumerable set; Recursively inseparable sets; Reduction (recursion theory); Reverse mathematics; Richardson's theorem; Simple set; Slow-growing hierarchy; Smn theorem; Trakhtenbrot's theorem; Turing degree; Turing jump; Turing machine; Utm theorem; Effective descriptive set theory; Lightface analytic game; Probabilistically checkable proof; IP (complexity); PP (complexity); Arthur–Merlin protocol; BQP; BPP (complexity); RP (complexity); ZPP (complexity); RL (complexity); Non-deterministic Turing machine; Crossing sequence (Turing machines); Langton's ant; Machine that always halts; Multi-string Turing machine with input and output; Multi-track Turing machine; Multitape Turing machine; Post–Turing machine; Probabilistic Turing machine; Quantum Turing machine; Read-only right moving Turing machines; Read-only Turing machine; Turing completeness; Turing machine equivalents; Turing machine examples; Turing machine gallery; Turing Machine simulator; Turing switch; Turmite; Universal Turing machine; Wang B-machine; Wolfram's 2-state 3-symbol Turing machine; Zeno machine