In computational complexity theory, the Immerman–Szelepcsényi theorem states that nondeterministic space complexity classes are closed under complementation. It 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. The result solved the second LBA problem.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Satz von Immerman und Szelepcsényi (de)
- Immerman–Szelepcsényi theorem (en)
- Théorème d'Immerman-Szelepcsényi (fr)
- Teorema de Immerman–Szelepcsényi (pt)
|
| rdfs:comment
| - Der Satz von Immerman und Szelepcsényi ist ein Satz aus der Komplexitätstheorie und besagt, dass die nichtdeterministischen Platzkomplexitätsklassen unter Komplementbildung abgeschlossen sind. Insbesondere ist daher die Klasse NL (nichtdeterministisch logarithmischer Platz) unter Komplementbildung abgeschlossen. Lange nahm man wie für die nichtdeterministischen Zeitkomplexitätsklassen an, dass NL nicht unter dem Komplement abgeschlossen sei, bis 1988 Immerman und Szelepcsényi unabhängig voneinander den Beweis erbrachten. Dafür wurde beiden gemeinsam der Gödel-Preis (1995) verliehen. (de)
- Le théorème d'Immerman-Szelepcsényi est un théorème d'informatique théorique, et notamment de la théorie de la complexité, démontré en 1987 indépendamment par Neil Immerman et Róbert Szelepcsényi, et qui leur a valu d'obtenir conjointement le prix Gödel en 1995. Une version simplifiée de ce théorème est NL = co-NL. (fr)
- In computational complexity theory, the Immerman–Szelepcsényi theorem states that nondeterministic space complexity classes are closed under complementation. It 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. The result solved the second LBA problem. (en)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - Der Satz von Immerman und Szelepcsényi ist ein Satz aus der Komplexitätstheorie und besagt, dass die nichtdeterministischen Platzkomplexitätsklassen unter Komplementbildung abgeschlossen sind. Insbesondere ist daher die Klasse NL (nichtdeterministisch logarithmischer Platz) unter Komplementbildung abgeschlossen. Lange nahm man wie für die nichtdeterministischen Zeitkomplexitätsklassen an, dass NL nicht unter dem Komplement abgeschlossen sei, bis 1988 Immerman und Szelepcsényi unabhängig voneinander den Beweis erbrachten. Dafür wurde beiden gemeinsam der Gödel-Preis (1995) verliehen. (de)
- In computational complexity theory, the Immerman–Szelepcsényi theorem states that nondeterministic space complexity classes are closed under complementation. It 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. The result solved the second LBA problem. In other words, if a nondeterministic machine can solve a problem, another machine with the same resource bounds can solve its complement problem (with the yes and no answers reversed) in the same asymptotic amount of space. No similar result is known for the time complexity classes, and indeed it is conjectured that NP is not equal to co-NP. The principle used to prove the theorem has become known as . It has also been used to prove other theorems in computational complexity, including the closure of LOGCFL under complementation and the existence of error-free randomized logspace algorithms for USTCON. (en)
- Le théorème d'Immerman-Szelepcsényi est un théorème d'informatique théorique, et notamment de la théorie de la complexité, démontré en 1987 indépendamment par Neil Immerman et Róbert Szelepcsényi, et qui leur a valu d'obtenir conjointement le prix Gödel en 1995. Une version simplifiée de ce théorème est NL = co-NL. (fr)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)