Structural complexity theory
In computational complexity theory of computer science, the structural complexity theory or simply structural complexity is the study of complexity classes, rather than computational complexity of individual problems and algorithms. It involves the research of both internal structures of various complexity classes and the relations between different complexity classes.
- Comment
- enIn computational complexity theory of computer science, the structural complexity theory or simply structural complexity is the study of complexity classes, rather than computational complexity of individual problems and algorithms. It involves the research of both internal structures of various complexity classes and the relations between different complexity classes.
- Depiction
- Has abstract
- enIn computational complexity theory of computer science, the structural complexity theory or simply structural complexity is the study of complexity classes, rather than computational complexity of individual problems and algorithms. It involves the research of both internal structures of various complexity classes and the relations between different complexity classes.
- Is primary topic of
- Structural complexity theory
- Label
- enStructural complexity theory
- Link from a Wikipage to another Wikipage
- Boolean satisfiability problem
- Bounded-error probabilistic polynomial
- Category:Structural complexity theory
- Complete language
- Complexity class
- Compression theorem
- Computable function
- Computational complexity theory
- Computer science
- Decision problem
- Deterministic Turing machine
- File:Polynomial time hierarchy.svg
- Gödel Prize
- Immerman–Szelepcsényi theorem
- Isolation lemma
- Leslie Valiant
- Linear bounded automaton
- Neil Immerman
- NL (complexity)
- NP (complexity)
- NSPACE
- P (complexity)
- P = NP problem
- Padding argument
- PH (complexity)
- Polynomial hierarchy
- Polynomial time hierarchy
- Reduction (complexity)
- Róbert Szelepcsényi
- RP (complexity)
- Savitch's theorem
- Seinosuke Toda
- Sipser–Lautemann theorem
- Space complexity
- Space hierarchy theorem
- Theoretical computer science
- Time hierarchy theorem
- Toda's theorem
- Turing machine
- Valiant–Vazirani theorem
- Vijay Vazirani
- Walter Savitch
- SameAs
- 4vHXm
- m.04y976
- Q7625020
- Teoria da complexidade estrutural
- 結構複雜度理論
- Subject
- Category:Structural complexity theory
- Thumbnail
- WasDerivedFrom
- Structural complexity theory?oldid=1106803357&ns=0
- WikiPageLength
- 5913
- Wikipage page ID
- 20188597
- Wikipage revision ID
- 1106803357
- WikiPageUsesTemplate
- Template:About
- Template:Citation needed
- Template:Main
- Template:Reflist
