I'm looking for some clarification on some concepts/facts I came across while studying for a class.
I was reading the following wikipedia article. The below specific section and statement intrigued me when looking it over.
http://en.wikipedia.org/wiki/Computational_complexity_theory#Important_complexity_classes "It turns out that PSPACE = NPSPACE and EXPSPACE = NEXPSPACE by Savitch's theorem"
I also read that NTMs can be simulated by DTMs but that the shortest accepting computation of the DTM is exponential with respect to the shortest accepting computation of the target NTM.
My questions are:
1.) Are PSPACE and NPSPACE the set of all problems that require at least polynomial space to be solved on Deterministic and Non-deterministic Turing machines respectively?
2.) If so, is the actual size of the polynomial space required dependent on the size of the input?
3.) For P and NP, they are each the sets of problems that require at least polynomial time to be solved on DTMs and NTMs respectively correct?
4.) Is the reason that the shortest accepting computation of a DTM simulating a target NTM is exponential with respect to the shortest accepting computation of an NTM due to the exponential explosion of the number of configurations that an NTM supports as input grows for a given problem?
5.) My last and overarching question is: Are the differences in the set of problems that can be solved in polynomial time on DTMs versus NTMs related to time/space tradeoffs where DTMs can't run some polynomial NTM algorithms in polynomial time because they don't have the same "space" that an NTM has available to it?
I'd also appreciate any reading you can suggest to me on time/space tradeoffs and NTMs versus DTMs.