Structural complexity theory: Difference between revisions
No edit summary |
Maxeto0910 (talk | contribs) m Removed double links in subsections. Tags: Visual edit Mobile edit Mobile web edit Advanced mobile edit |
||
| Line 11: | Line 11: | ||
===The compression theorem=== |
===The compression theorem=== |
||
{{main|Compression theorem}} |
{{main|Compression theorem}} |
||
The |
The compression theorem is an important theorem about the complexity of [[computable function]]s. |
||
The theorem states that there exists no largest [[complexity class]], with computable boundary, which contains all computable functions. |
The theorem states that there exists no largest [[complexity class]], with computable boundary, which contains all computable functions. |
||
| Line 17: | Line 17: | ||
===Space hierarchy theorems=== |
===Space hierarchy theorems=== |
||
{{main|Space hierarchy theorem}} |
{{main|Space hierarchy theorem}} |
||
The |
The space hierarchy theorems are separation results that show that both deterministic and nondeterministic machines can solve more problems in (asymptotically) more space, subject to certain conditions. For example, a [[deterministic Turing machine]] can solve more [[decision problem]]s in space ''n'' log ''n'' than in space ''n''. The somewhat weaker analogous theorems for time are the [[time hierarchy theorem]]s. |
||
===Time hierarchy theorems=== |
===Time hierarchy theorems=== |
||
{{main|Time hierarchy theorem}} |
{{main|Time hierarchy theorem}} |
||
The |
The time hierarchy theorems are important statements about time-bounded computation on [[Turing machine]]s. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example, there are problems that can be solved with ''n''<sup>2</sup> time but not ''n'' time. |
||
===Valiant–Vazirani theorem=== |
===Valiant–Vazirani theorem=== |
||
{{main|Valiant–Vazirani theorem}} |
{{main|Valiant–Vazirani theorem}} |
||
The |
The Valiant–Vazirani theorem is a theorem in [[computational complexity theory]]. It was proven by [[Leslie Valiant]] and [[Vijay Vazirani]] in their paper titled ''NP is as easy as detecting unique solutions'' published in 1986.<ref>{{Cite journal | last1 = Valiant | first1 = L. | last2 = Vazirani | first2 = V.| doi = 10.1016/0304-3975(86)90135-0 | title = NP is as easy as detecting unique solutions | url = http://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/NP_is_as.pdf| journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]] | volume = 47 | pages = 85–93 | year = 1986 | doi-access = free }}</ref> |
||
The theorem states that if there is a [[P (complexity)|polynomial time algorithm]] for [[Boolean satisfiability problem#Extensions of SAT|Unambiguous-SAT]], then [[NP (complexity)|NP]]=[[RP (complexity)|RP]]. |
The theorem states that if there is a [[P (complexity)|polynomial time algorithm]] for [[Boolean satisfiability problem#Extensions of SAT|Unambiguous-SAT]], then [[NP (complexity)|NP]]=[[RP (complexity)|RP]]. |
||
The proof is based on the Mulmuley–Vazirani [[isolation lemma]], which was subsequently used for a number of important applications in [[theoretical computer science]]. |
The proof is based on the Mulmuley–Vazirani [[isolation lemma]], which was subsequently used for a number of important applications in [[theoretical computer science]]. |
||
| Line 31: | Line 31: | ||
===Sipser–Lautemann theorem=== |
===Sipser–Lautemann theorem=== |
||
{{main|Sipser–Lautemann theorem}} |
{{main|Sipser–Lautemann theorem}} |
||
The |
The Sipser–Lautemann theorem or '''Sipser–Gács–Lautemann theorem''' states that [[Bounded-error probabilistic polynomial|Bounded-error Probabilistic Polynomial]] (BPP) time, is contained in the [[Polynomial hierarchy|polynomial time hierarchy]], and more specifically Σ<sub>2</sub> ∩ Π<sub>2</sub>. |
||
===Savitch's theorem=== |
===Savitch's theorem=== |
||
{{main|Savitch's theorem}} |
{{main|Savitch's theorem}} |
||
Savitch's theorem, proved by [[Walter Savitch]] in 1970, gives a relationship between deterministic and non-deterministic [[space complexity]]. It states that for any function <math>f\in\Omega(\log(n))</math>, |
|||
:<math>\mathsf{NSPACE}\left(f\left(n\right)\right) \subseteq \mathsf{DSPACE}\left(\left(f\left(n\right)\right)^2\right).</math> |
:<math>\mathsf{NSPACE}\left(f\left(n\right)\right) \subseteq \mathsf{DSPACE}\left(\left(f\left(n\right)\right)^2\right).</math> |
||
| Line 41: | Line 41: | ||
===Toda's theorem=== |
===Toda's theorem=== |
||
{{main|Toda's theorem}} |
{{main|Toda's theorem}} |
||
Toda's theorem is a result that was proven by [[Seinosuke Toda]] in his paper "PP is as Hard as the Polynomial-Time Hierarchy" (1991) and was given the 1998 [[Gödel Prize]]. The theorem states that the entire [[PH (complexity)|polynomial hierarchy PH]] is contained in P<sup>PP</sup>; this implies a closely related statement, that PH is contained in P<sup>#P</sup>. |
|||
===Immerman–Szelepcsényi theorem=== |
===Immerman–Szelepcsényi theorem=== |
||
{{main|Immerman–Szelepcsényi theorem}} |
{{main|Immerman–Szelepcsényi theorem}} |
||
The |
The Immerman–Szelepcsényi theorem was proven independently by [[Neil Immerman]] and [[Róbert Szelepcsényi]] in 1987, for which they shared the 1995 [[Gödel Prize]]. In its general form the theorem states that [[NSPACE]](''s''(''n'')) = co-NSPACE(''s''(''n'')) for any function ''s''(''n'') ≥ log ''n''. The result is equivalently stated as [[NL (complexity)|NL]] = co-NL; although this is the special case when ''s''(''n'') = log ''n'', it implies the general theorem by a standard [[padding argument]]{{Citation needed|date=July 2010}}. The result solved the [[linear bounded automaton#LBA problems|second LBA problem]]. |
||
==Research topics== |
==Research topics== |
||
Major directions of research in this area include:<ref name=jha/> |
Major directions of research in this area include:<ref name=jha/> |
||
Latest revision as of 08:43, 22 October 2023
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.[1]
History
[edit]The theory has emerged as a result of (still failing) attempts to resolve the first and still the most important question of this kind, the P = NP problem. Most of the research is done basing on the assumption of P not being equal to NP and on a more far-reaching conjecture that the polynomial time hierarchy of complexity classes is infinite.[1]
Important results
[edit]The compression theorem
[edit]The compression theorem is an important theorem about the complexity of computable functions.
The theorem states that there exists no largest complexity class, with computable boundary, which contains all computable functions.
Space hierarchy theorems
[edit]The space hierarchy theorems are separation results that show that both deterministic and nondeterministic machines can solve more problems in (asymptotically) more space, subject to certain conditions. For example, a deterministic Turing machine can solve more decision problems in space n log n than in space n. The somewhat weaker analogous theorems for time are the time hierarchy theorems.
Time hierarchy theorems
[edit]The time hierarchy theorems are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example, there are problems that can be solved with n2 time but not n time.
Valiant–Vazirani theorem
[edit]The Valiant–Vazirani theorem is a theorem in computational complexity theory. It was proven by Leslie Valiant and Vijay Vazirani in their paper titled NP is as easy as detecting unique solutions published in 1986.[2] The theorem states that if there is a polynomial time algorithm for Unambiguous-SAT, then NP=RP. The proof is based on the Mulmuley–Vazirani isolation lemma, which was subsequently used for a number of important applications in theoretical computer science.
Sipser–Lautemann theorem
[edit]The Sipser–Lautemann theorem or Sipser–Gács–Lautemann theorem states that Bounded-error Probabilistic Polynomial (BPP) time, is contained in the polynomial time hierarchy, and more specifically Σ2 ∩ Π2.
Savitch's theorem
[edit]Savitch's theorem, proved by Walter Savitch in 1970, gives a relationship between deterministic and non-deterministic space complexity. It states that for any function ,
Toda's theorem
[edit]Toda's theorem is a result that was proven by Seinosuke Toda in his paper "PP is as Hard as the Polynomial-Time Hierarchy" (1991) and was given the 1998 Gödel Prize. The theorem states that the entire polynomial hierarchy PH is contained in PPP; this implies a closely related statement, that PH is contained in P#P.
Immerman–Szelepcsényi theorem
[edit]The Immerman–Szelepcsényi theorem was proven independently by Neil Immerman and Róbert Szelepcsényi in 1987, for which they shared the 1995 Gödel Prize. In its general form the theorem states that NSPACE(s(n)) = co-NSPACE(s(n)) for any function s(n) ≥ log n. The result is equivalently stated as NL = co-NL; although this is the special case when s(n) = log n, it implies the general theorem by a standard padding argument[citation needed]. The result solved the second LBA problem.
Research topics
[edit]Major directions of research in this area include:[1]
- study of implications stemming from various unsolved problems about complexity classes
- study of various types of resource-restricted reductions and the corresponding complete languages
- study of consequences of various restrictions on and mechanisms of storage and access to data
References
[edit]- ^ a b c Juris Hartmanis, "New Developments in Structural Complexity Theory" (invited lecture), Proc. 15th International Colloquium on Automata, Languages and Programming, 1988 (ICALP 88), Lecture Notes in Computer Science, vol. 317 (1988), pp. 271-286.
- ^ Valiant, L.; Vazirani, V. (1986). "NP is as easy as detecting unique solutions" (PDF). Theoretical Computer Science. 47: 85–93. doi:10.1016/0304-3975(86)90135-0.