inde47d@jetson.uh.edu (04/24/91)
I am looking for a proof to the following statement. If a non deterministic turing machine requires a space s(n) for a problem, the same problem can be solved on a deterministic turing machine with a space complexity equal to s^2(n). I would appreciate very much if someone could tell me the proof or point out references for the same. Not being a student of computer science, I would very much appreciate intuitive proofs. Thank you Shiv e-mail: inde47d@jetson.uh.edu