Immerman–Szelepcsényi theorem
id:
immerman-szelepcs-nyi-theorem-240-14050736
title:
Immerman–Szelepcsényi theorem
text:
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 t
brand slug:
wiki
category slug:
encyclopedia
description:
Closure of nondeterministic space under complementation
original url:
https://en.wikipedia.org/wiki/Immerman%E2%80%93Szelepcs%C3%A9nyi_theorem
date created:
date modified:
2024-03-23T08:08:22Z
main entity:
{"identifier":"Q744440","url":"https://www.wikidata.org/entity/Q744440"}
image:
fields total:
13
integrity:
14