Consider the following 2-person game. The game is played on an n Times n \"board

Question

Consider the following 2-person game. The game is played on an n Times n "board" with non-negative integers in each of the n^2 cells. There is a specified "target" value B which is also a nonnegative integer. The players take turns selecting integers from successive rows: player one selects an integer in row 1, then player two selects an integer in row 2, then player one selects an integer in row 3, etc ellipsis After an integer has been selected from the last row, the game ends. If the sum of all of the selected integers equals B, then player 1 wins; otherwise player 2 wins. Given a game board (a square matrix M of nonnegative integers) and a nonnegative integer B, we can ask whether there is a win for player one (i.e., player one can win no matter what player two does). Prove that the language L consisting of pairs (M, B) for which there is a win for player one is PSPACE-complete. In other words prove: L is in PSPACE-complete:

Explanation / Answer

A decision problem is PSPACE-complete if it can be solved using an
amount of memory that is polynomial in the input length (polynomial space)
and if every other problem that can be solved in polynomial space can be transformed
to it in polynomial time.

For the given problem, we have an input size of O(n2).

The game will end at the last row after both players reach the last row.
So, there are O(n2) positions to traverse.

On reaching the last row, if the sum of all the selected integers equals B, player 1
wins else the player 2 wins. To check the sum as equal to B can happen in polynomial time.

Also, here the problem speaks about the winning strategy and hence a draw is treated as defeat.

With input being of O(n2) and positions to traverse is less than O(n2) and the deciding whether
the sum equals B all happens in polynomial time.

So, this problem satisfies all the conditions for it to be PSPACE-complete.

And hence this is PSPACE-complete.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.