The Immerman–Szelepcsényi theorem states that nondeterministic space complexity classes are closed under complementation, meaning that if a nondeterministic machine can solve a problem, another machine with the same resource bounds can solve its complement problem. It was proven in 1987 and solved the second LBA problem. The principle used to prove the theorem has been used to prove other theorems in computational complexity.
Carnegie Mellon University
Spring 2023
This course provides an initial dive into complexity theory, exploring computations bound by resources like time, space, and energy. Emphasis is placed on low complexity classes.
No concepts data
+ 29 more concepts