Savitch's theorem
Relation between deterministic and nondeterministic space complexity / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Savitch's theorem?
Summarize this article for a 10 year old
SHOW ALL QUESTIONS
In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, gives a relationship between deterministic and non-deterministic space complexity. It states that for any function ,
In other words, if a nondeterministic Turing machine can solve a problem using space, a deterministic Turing machine can solve the same problem in the square of that space bound.[1] Although it seems that nondeterminism may produce exponential gains in time (as formalized in the unproven exponential time hypothesis), Savitch's theorem shows that it has a markedly more limited effect on space requirements.[2]