I'm reading a definition of PSPACE and say: are the decision problems solvable in polynomial space on a Deterministic Turing Machine. My question is: Why NP is in PSPACE?. I have a doubt beccause for example a SAT problem is solvable in Non-Deterministic Turing Machine and SAT $\in NP$ and not in $P$.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
NP is a complexity class with constraints on time, whilst PSPACE is a complexity class with constraints on space. The difference between time and space is (in this case) simple: Space can be reused, whilst Time cannot. A Space-bounded machine can run for as long as it wants (as long as it terminates).
Therefore we can construct a PSPACE-Machine that solves SAT: The machine simply tries every solution.
-
$\begingroup$ yes, but in book say solvable in polynomial space on a Deterministic Turing Machine, then my question is how implement SAT in Deterministic Turing Machine? $\endgroup$– juaninfCommented Dec 6, 2013 at 12:27
-
2$\begingroup$ You iterate through every solution. It takes a lot of time, but it doesn't use so much space, and works on a deterministic turing machine. $\endgroup$– Mike B.Commented Dec 6, 2013 at 12:30
-
6$\begingroup$ Just to elaborate on the last point, the PSPACE machine, one by one, writes down satisfying assignments for the SAT instance. Each on of these only takes $O(n)$ space - we just need True or False for each variable. After writing down the assignment, it checks whether it satisfies the formula or not. If it does, then it answers YES. If not, it wipes that assignment, and reuses the same space to write the next one. It only says no if it gets through all the assignments and nothing worked. There's no nondeterminism, it takes $O(2^{n})$ time but we don't care as it uses only $O(n)$ space. $\endgroup$ Commented Dec 6, 2013 at 12:31
-
$\begingroup$ @MikeB. but the time, (of your algorithm proposed) is not polynomial then SAT can't implement in deterministic turing machine. Then my question again is how implement SAT in Deterministic Turing Machine? $\endgroup$– juaninfCommented Dec 6, 2013 at 12:37
-
4$\begingroup$ @juaninf To first answer the question to Mike B., deterministic doesn't mean polynomial it just means it can't use nondeterministism. So a machine for PSPACE is 1) deterministic and 2) uses polynomial space. There's no conditions about how long it takes. Then to answer the question to me, we've outlined a deterministic algorithm that takes polynomial space to solve SAT. Now as SAT is NP-complete, we can deterministically and in polynomial time and hence space reduce any instance of any problem in NP to an equivalent SAT instance, which we can then solve. $\endgroup$ Commented Dec 6, 2013 at 13:14