Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

So there is a n x n game board and each location on the board has an integer. Player one picks a number from row 1 and player 2 picks a number from row 2 and they alternate until there are no more rows. Then they add up all the numbers and player 1 wins if the sum is equal to a predetermined sum S, player 2 wins otherwise. A winning strategy for player 1 for a particular board and sum (B, S) is if player 1 can win no matter what player 2 does. I want to show that this problem is PSpace-complete

So first I have to show that it's in PSpace, which I think is pretty easy because the total number of moves is bound by the size of the board, which is n^2.

I am getting stuck on showing that it's PSpace-hard though, I know I have to reduce from QSAT, but I can't figure out how. Can someone help?

EDIT: Would each square be a variable? Where 'true' means that square is selected and 'false' means otherwise? Somehow the definition of QSAT makes it sound like each variable should represent a row since in the case of universal quantifier, it doesn't matter what the value of the variable, just like it doesn't matter the row. But each boolean quantifier has 2 values where each row can have n.

share|cite|improve this question
You may want to take the question to brand-new cs.SE! – Raphael Mar 23 '12 at 23:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.