Structural complexity theory - Revision history

Maxeto0910: Removed double links in subsections.

2023-10-22T08:43:50Z

Removed double links in subsections.

2A02:1812:110C:DC00:4D2B:9852:1A32:B76F at 11:54, 9 May 2023

2023-05-09T11:54:26Z

← Previous revision		Revision as of 11:54, 9 May 2023
Line 2:		Line 2:
	[[Image:Polynomial time hierarchy.svg\|250px\|thumb\|right\|Pictorial representation of the polynomial time hierarchy. The arrows denote inclusion.]]		[[Image:Polynomial time hierarchy.svg\|250px\|thumb\|right\|Pictorial representation of the polynomial time hierarchy. The arrows denote inclusion.]]

	In [[computational complexity theory]] of [[computer science]], the '''structural complexity theory''' or simply '''structural complexity''' is the study of [[complexity class]]es, 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.<ref name=jha>[[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.</ref>		In [[computational complexity theory]] of [[computer science]], the '''structural complexity theory''' or simply '''structural complexity''' is the study of [[complexity class]]es, 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.<ref name=jha>[[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.</ref>

	==History==		==History==
Line 25:		Line 25:
	===Valiant–Vazirani theorem===		===Valiant–Vazirani theorem===
	{{main\|Valiant–Vazirani theorem}}		{{main\|Valiant–Vazirani theorem}}
	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 \| volume = 47 \| pages = 85–93 \| year = 1986 \| doi-access = free }}</ref>		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]].

Nihiltres: Standardized hatnote

2022-08-26T14:51:58Z

Standardized hatnote

← Previous revision		Revision as of 14:51, 26 August 2022
Line 1:		Line 1:
	~~:''This page is~~ about ~~structural complexity theory~~ in ~~computational complexity theory of~~ computer science. ~~For structural complexity~~ in applied mathematics ~~see [[structural~~ complexity (applied mathematics)~~]].''~~		{{about\|the area in computer science\|the area in applied mathematics\|Structural complexity (applied mathematics)}}

	[[Image:Polynomial time hierarchy.svg\|250px\|thumb\|right\|Pictorial representation of the polynomial time hierarchy. The arrows denote inclusion.]]		[[Image:Polynomial time hierarchy.svg\|250px\|thumb\|right\|Pictorial representation of the polynomial time hierarchy. The arrows denote inclusion.]]

OAbot: Open access bot: doi added to citation with #oabot.

2021-07-05T14:32:35Z

Open access bot: doi added to citation with #oabot.

← Previous revision		Revision as of 14:32, 5 July 2021
Line 26:		Line 26:
	===Valiant–Vazirani theorem===		===Valiant–Vazirani theorem===
	{{main\|Valiant–Vazirani theorem}}		{{main\|Valiant–Vazirani theorem}}
	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 \| volume = 47 \| pages = 85–93 \| year = 1986 }}</ref>		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 \| 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]].

Monkbot: Task 18 (cosmetic): eval 1 template: del empty params (2×);

2020-12-15T05:29:39Z

Task 18 (cosmetic): eval 1 template: del empty params (2×);

← Previous revision		Revision as of 05:29, 15 December 2020
Line 26:		Line 26:
	===Valiant–Vazirani theorem===		===Valiant–Vazirani theorem===
	{{main\|Valiant–Vazirani theorem}}		{{main\|Valiant–Vazirani theorem}}
	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 \| volume = 47 \| pages = 85–93 \| year = 1986 ~~\| pmid = \| pmc =~~ }}</ref>		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 \| volume = 47 \| pages = 85–93 \| year = 1986 }}</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]].

62.74.10.222 at 08:06, 26 June 2019

2019-06-26T08:06:13Z

← Previous revision		Revision as of 08:06, 26 June 2019
Line 1:		Line 1:
	:''This page is about structural complexity theory in computational complexity theory of computer science. For structural complexity in applied mathematics see [[structural complexity (applied mathematics)]]''		:''This page is about structural complexity theory in computational complexity theory of computer science. For structural complexity in applied mathematics see [[structural complexity (applied mathematics)]].''

	[[Image:Polynomial time hierarchy.svg\|250px\|thumb\|right\|Pictorial representation of the polynomial time hierarchy. The arrows denote inclusion.]]		[[Image:Polynomial time hierarchy.svg\|250px\|thumb\|right\|Pictorial representation of the polynomial time hierarchy. The arrows denote inclusion.]]

83.81.25.98 at 14:20, 9 March 2018

2018-03-09T14:20:35Z

← Previous revision		Revision as of 14:20, 9 March 2018
Line 46:		Line 46:
	===Immerman–Szelepcsényi theorem===		===Immerman–Szelepcsényi theorem===
	{{main\|Immerman–Szelepcsényi theorem}}		{{main\|Immerman–Szelepcsényi theorem}}
	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}}. ~~Tghjkgjhhe~~ result solved the [[linear bounded automaton#LBA problems\|second LBA problem]].		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/>

83.81.25.98 at 14:19, 9 March 2018

2018-03-09T14:19:50Z

← Previous revision		Revision as of 14:19, 9 March 2018
Line 46:		Line 46:
	===Immerman–Szelepcsényi theorem===		===Immerman–Szelepcsényi theorem===
	{{main\|Immerman–Szelepcsényi theorem}}		{{main\|Immerman–Szelepcsényi theorem}}
	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]].		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}}. Tghjkgjhhe 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/>

Cedar101: /* Savitch's theorem */ \mathsf

2016-09-29T05:09:33Z

Savitch's theorem: \mathsf

← Previous revision		Revision as of 05:09, 29 September 2016
Line 38:		Line 38:
	[[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>,		[[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>\~~text~~{NSPACE}\left(f\left(n\right)\right) \subseteq \~~text~~{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>

	===Toda's theorem===		===Toda's theorem===

Einstein2: new key for Category:Structural complexity theory: " " using HotCat

2015-10-15T15:55:23Z

new key for Category:Structural complexity theory: " " using HotCat

← Previous revision		Revision as of 15:55, 15 October 2015
Line 56:		Line 56:
	{{reflist}}		{{reflist}}

	[[Category:Structural complexity theory]]		[[Category:Structural complexity theory\| ]]

← Previous revision		Revision as of 08:43, 22 October 2023
Line 11:		Line 11:
	===The compression theorem===		===The compression theorem===
	{{main\|Compression theorem}}		{{main\|Compression theorem}}
	The [[compression theorem]] is an important theorem about the complexity of [[computable function]]s.		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 [[space hierarchy ~~theorem]]s~~ 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.		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 [[time hierarchy ~~theorem]]s~~ 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.		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 [[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 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 [[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>.		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>,		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>.		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 [[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]].		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/>