I want to prove that Mixed Quantified Horn SAT is a PSPACE-complete problem. I have proved that it is PSPACE-hard. How can I prove that it is in PSPACE?

My study: To prove QSAT to be in PSPACE: Generate a boolean tree or circuit and evaluated it in O(n) space. Similarly, it has been done for the "Geography " problem and "GO" problem. SO, I think it should be possible to do for the mixedQhorn problem in the same way.

  • $\begingroup$ What have you tried? Where did you get stuck? We expect you to make a serious effort before asking, and to show us what you have tried. Have you looked at proofs that other problems are in PSPACE, and did you understand those proofs? Have you tried mimicing them? The Wikipedia article on PSPACE explains the definition of PSPACE, from which you can infer one way to prove that a language is in PSPACE: use the definition. $\endgroup$ – D.W. Jun 20 '14 at 19:42
  • $\begingroup$ @D.W.: I have added my thought. $\endgroup$ – Curious Jun 20 '14 at 21:00
  • 1
    $\begingroup$ I don't understand what you tried. Generate a boolean tree or circuit: What tree/circuit did you have in mind? How is the tree or circuit generated from the formula, and why would it show that your problem is in PSPACE? I think you have left out some details, which makes it hard to provide specific feedback on your approach. Anyway, when you tried using that approach to prove that this is in PSPACE, where did you get stuck? Did you understand the proof that QSAT is in PSPACE? $\endgroup$ – D.W. Jun 20 '14 at 21:03

To show that a problem is in PSPACE is quite straightforward: you show that it can be solved by a deterministic Turing Machine using polynomial space.

So basically you just write an algorithm solving the problem. You can use as much time as you like, as long as you only ever use a polynomial amount of memory.

  • $\begingroup$ Thanks. So as we know that a quantified boolean formula is in pspace and we show this by saying that by checking every assignment. So, how to show it for mixed quantified horn formula? $\endgroup$ – Curious Jun 20 '14 at 16:52
  • $\begingroup$ I have done the "completeness" part but have no idea on the PSAPCE proof. $\endgroup$ – Curious Jun 20 '14 at 18:22
  • 1
    $\begingroup$ What have you tried for that? Can you think of an algorithm solving the problem? We can help you and give you advice, but we won't just do it for you. $\endgroup$ – jmite Jun 20 '14 at 19:46
  • $\begingroup$ Added my work in the question $\endgroup$ – Curious Jun 20 '14 at 20:50
  • $\begingroup$ @jmite Even better: when it can be solved by a nondeterministic TM (using polynomial space). Thanks to Savitch. So we can do some clever guessing where appropriate. $\endgroup$ – Hendrik Jan Jun 21 '14 at 10:15

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.