Skip to main content
Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

6
  • $\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$ Commented 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$ 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$ Commented 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