Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!menudo.uh.edu!jetson.uh.edu!inde47d
From: inde47d@jetson.uh.edu
Newsgroups: comp.theory
Subject: Help on space complexity
Message-ID: <9217.281597b9@jetson.uh.edu>
Date: 24 Apr 91 14:35:35 CDT
Organization: University of Houston
Lines: 12

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