Immerman–Szelepcsényi theorem
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.
2-satisfiabilityAlternating Turing machineComplement (complexity)Context-sensitive grammarContext-sensitive languageDescriptive ComplexityFinite model theoryGödel PrizeImmerman-Szelepcsenyi TheoremImmerman-Szelepcsenyi theoremImmerman-Szelepcsényi TheoremImmerman-Szelepcsényi theoremImmerman–Szelepcsenyi theoremLinear bounded automatonList of Cornell University alumni (natural sciences)List of multiple discoveriesList of theoremsNL-completeNL (complexity)NSPACENeil ImmermanRóbert SzelepcsényiSavitch's theoremSpace complexitySpace hierarchy theoremSt-connectivityState complexityStructural complexity theory
Link from a Wikipage to another Wikipage
primaryTopic
Immerman–Szelepcsényi theorem
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.
has abstract
Le théorème d'Immerman-Szelepc ...... de ce théorème est NL = co-NL.
@fr
Link from a Wikipage to an external page
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
1,025,786,689
Link from a Wikipage to another Wikipage
wikiPageUsesTemplate
subject
comment
Le théorème d'Immerman-Szelepc ...... de ce théorème est NL = co-NL.
@fr
label
Immerman–Szelepcsényi theorem
@en
Satz von Immerman und Szelepcsényi
@de
Teorema de Immerman–Szelepcsényi
@pt
Théorème d'Immerman-Szelepcsényi
@fr