# Structural complexity theory > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Structural_complexity_theory > Markdown URL: https://mediated.wiki/source/Structural_complexity_theory.md > Source: https://en.wikipedia.org/wiki/Structural_complexity_theory > Source revision: 1333498926 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) This article is about the area in computer science. For the area in applied mathematics, see [Structural complexity (applied mathematics)](/source/Structural_complexity_(applied_mathematics)). In [computational complexity theory](/source/Computational_complexity_theory) of [computer science](/source/Computer_science), the **structural complexity theory** or simply **structural complexity** is the study of [complexity classes](/source/Complexity_class), 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 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](/source/P_%3D_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](/source/Polynomial_time_hierarchy) of complexity classes is infinite.[1] ## Important results ### The compression theorem Main article: [Compression theorem](/source/Compression_theorem) The compression theorem is an important theorem about the complexity of [computable functions](/source/Computable_function). The theorem states that there exists no largest [complexity class](/source/Complexity_class), with computable boundary, which contains all computable functions. ### Space hierarchy theorems Main article: [Space hierarchy theorem](/source/Space_hierarchy_theorem) 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](/source/Deterministic_Turing_machine) can solve more [decision problems](/source/Decision_problem) in space *n* log *n* than in space *n*. The somewhat weaker analogous theorems for time are the [time hierarchy theorems](/source/Time_hierarchy_theorem). ### Time hierarchy theorems Main article: [Time hierarchy theorem](/source/Time_hierarchy_theorem) The time hierarchy theorems are important statements about time-bounded computation on [Turing machines](/source/Turing_machine). 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*2 time but not *n* time. ### Valiant–Vazirani theorem Main article: [Valiant–Vazirani theorem](/source/Valiant%E2%80%93Vazirani_theorem) The Valiant–Vazirani theorem is a theorem in [computational complexity theory](/source/Computational_complexity_theory). It was proven by [Leslie Valiant](/source/Leslie_Valiant) and [Vijay Vazirani](/source/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](/source/P_(complexity)) for [Unambiguous-SAT](/source/Boolean_satisfiability_problem#Extensions_of_SAT), then [NP](/source/NP_(complexity))=[RP](/source/RP_(complexity)). The proof is based on the Mulmuley–Vazirani [isolation lemma](/source/Isolation_lemma), which was subsequently used for a number of important applications in [theoretical computer science](/source/Theoretical_computer_science). ### Sipser–Lautemann theorem Main article: [Sipser–Lautemann theorem](/source/Sipser%E2%80%93Lautemann_theorem) The Sipser–Lautemann theorem or **Sipser–Gács–Lautemann theorem** states that [Bounded-error Probabilistic Polynomial](/source/BPP_(complexity)) (BPP) time, is contained in the [polynomial time hierarchy](/source/Polynomial_hierarchy), and more specifically Σ2 ∩ Π2. ### Savitch's theorem Main article: [Savitch's theorem](/source/Savitch's_theorem) Savitch's theorem, proved by [Walter Savitch](/source/Walter_Savitch) in 1970, gives a relationship between deterministic and non-deterministic [space complexity](/source/Space_complexity). It states that for any function f\in\Omega(\log(n)), - \mathsf{NSPACE}\left(f\left(n\right)\right) \subseteq \mathsf{DSPACE}\left(\left(f\left(n\right)\right)^2\right). ### Toda's theorem Main article: [Toda's theorem](/source/Toda's_theorem) Toda's theorem is a result that was proven by [Seinosuke Toda](/source/Seinosuke_Toda) in his paper "PP is as Hard as the Polynomial-Time Hierarchy" (1991) and was given the 1998 [Gödel Prize](/source/G%C3%B6del_Prize). The theorem states that the entire [polynomial hierarchy PH](/source/PH_(complexity)) is contained in PPP; this implies a closely related statement, that PH is contained in P#P. ### Immerman–Szelepcsényi theorem Main article: [Immerman–Szelepcsényi theorem](/source/Immerman%E2%80%93Szelepcs%C3%A9nyi_theorem) The Immerman–Szelepcsényi theorem was proven independently by [Neil Immerman](/source/Neil_Immerman) and [Róbert Szelepcsényi](/source/R%C3%B3bert_Szelepcs%C3%A9nyi) in 1987, for which they shared the 1995 [Gödel Prize](/source/G%C3%B6del_Prize). In its general form the theorem states that [NSPACE](/source/NSPACE)(*s*(*n*)) = co-NSPACE(*s*(*n*)) for any function *s*(*n*) ≥ log *n*. The result is equivalently stated as [NL](/source/NL_(complexity)) = co-NL; although this is the special case when *s*(*n*) = log *n*, it implies the general theorem by a standard [padding argument](/source/Padding_argument)[citation needed]. The result solved the [second LBA problem](/source/Linear_bounded_automaton#LBA_problems). ## Research topics 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](/source/Reduction_(complexity)) and the corresponding [complete languages](/source/Complete_language) - study of consequences of various restrictions on and mechanisms of storage and access to data ## References 1. [Juris Hartmanis](/source/Juris_Hartmanis), "New Developments in Structural Complexity Theory" (invited lecture), Proc. 15th [International Colloquium on Automata, Languages and Programming](/source/International_Colloquium_on_Automata,_Languages_and_Programming), 1988 (ICALP 88), *[Lecture Notes in Computer Science](/source/Lecture_Notes_in_Computer_Science)*, vol. 317 (1988), pp. 271-286. 1. Valiant, L. & Vazirani, V. (1986). ["NP is as easy as detecting unique solutions"](http://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/NP_is_as.pdf). *[Theoretical Computer Science](/source/Theoretical_Computer_Science_(journal))*. **47**: 85–93. [doi:10.1016/0304-3975(86)90135-0](https://doi.org/10.1016/0304-3975(86)90135-0) --- Adapted from the Wikipedia article [Structural complexity theory](https://en.wikipedia.org/wiki/Structural_complexity_theory) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Structural_complexity_theory?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.