1
$\begingroup$

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$.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\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$ – juaninf Dec 6 '13 at 12:27
  • 1
    $\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. Dec 6 '13 at 12:30
  • 4
    $\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$ – Luke Mathieson Dec 6 '13 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$ – juaninf Dec 6 '13 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$ – Luke Mathieson Dec 6 '13 at 13:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.