First Let us review what is P, NP and NP-complete.
How to prove one problem is NP-complete?
- Just need to show that the problem of interest can be reduced from other NP-complete problem.
Example: Show Set-Cover is NP-complete.
Since Vertex Cover is NP-Complete, we just need to show Vertex Cover (leq_P) Set Cover, means every Vertex Cover problem can be reduced to a Set Cover problem.
PSPACE
TQSAT True Quantified SAT is PSPACE-complete.
https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/09PSPACE.pdf
It is easy to see TQSAT is PSPACE, but how to prove it is PSPACE-complete?
For TQSAT, the space requirement is the number of quantifiers in the formula, assuming the space can be reused.
However, the space required to stored the solution is exponential!?