3 ms·
So an exponential memory requirement implies that the theoretical time is not polynomial after all? I'm not sure. It seems possible that I would need to have e
by ronaldx 13y ago
So an exponential memory requirement implies that the theoretical time is not polynomial after all? I'm not sure.
It seems possible that I would need to have exponential memory but not necessarily to access it.
Is it true to say that memory not-accessed is not-needed? It's believable but not immediately obvious to me, and if it's false then there's no two-way implication.
Edit: apparently NP is a subset of PSPACE, so fair enough.
- heron87 13y agoNot sure what you mean by "memory requirement" and "theoretical time". If you don't access the memory, what do you mean by saying you "need" it? If a turing machine — or a computer program, for that matter — uses, i.e., "visits", exponentially many memory cells, then, indeed, its computing time cannot be polynomial. But note that every turing machine theoretically has infinite memory. The question is how much of it is actually used. PSPACE consists of those problems that can be solved by a turing machine that uses no more than p(n) memory, where p(n) is some polynomial in the input length n. Note that, for PSAPCE, time is unrestricted. So obviously P and NP are subsets of PSPACE, but it is unknown whether they are proper subsets.