0
$\begingroup$

I'm studying the Sipser textbook for my theory of complexity class. In a part of the book (i.e., Space Complexity chapter), for showing that Generalized Geography game is PSPACE-complete, the author has given an argument to model this game with TQBF problem (which is proven to be PSPACE-complete).

In a step of the argument, he has tried to construct a directed graph by using the definitions of TQBF problem (universal and existential quantifiers). What he has come up with is the following graph:

enter image description here

I have some questions about this graph:

  1. I, actually, don't get it why the diamond structure has been used for showing choice possibilities of player $x_i$. Couldn't we use a simple structure like what we do on binary trees?

enter image description here

  1. How would it be if we use a hexagon shape instead of diamond for showing choices of $x_i$?
Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Your graph based on a binary tree would have exponential size (it would require at least $2^k$ nodes), which is probably no good for the reduction; an exponential blow-up in the size of the problem instance isn't ok.

Yes, you could use a hexagon instead of a diamond. I don't see any advantage, but it would also provide a valid reduction.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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