Savitch's theorem states that for any function in Ω(log(n)), a nondeterministic Turing machine can solve a problem using f(n) space, while a deterministic Turing machine can solve the same problem in the square of that space bound. It shows that nondeterminism has limited effect on space requirements compared to time complexity.
Carnegie Mellon University
Spring 2015
A foundational course that introduces formal languages, automata, computability, and complexity theories, including finite automata, Turing machines, and P/NP classes.
No concepts data
+ 35 more concepts