Question: Are there any known proofs of Savitch's theorem that $NL \subseteq L^2$ besides the usual one?

By the usual one I mean the proof based on recursively querying whether there is a midpoint.

Whether a proof is different is subjective, but hopefully not too subjective for this forum.

What I Learned:

  • 1
    $\begingroup$ This is a really neat question! I know that this isn't what you asked, but I thought it might be valuable to mention the following. It's my understanding that it's not known whether $NL \subseteq DTISP(2^{o(\log^2(n))}, \log^2(n))$. In other words, maybe a different approach could improve on Savitch's theorem by running in $2^{o(\log^2(n))}$ time. $\endgroup$ – Michael Wehar Feb 12 '20 at 5:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.