Let $\mathrm{SpaceTMSat} = \{\langle M, w, 1^n\rangle\mid\text {DTM $M$ accepts $w$ in space }n\}$.

How do I prove that this language is PSPACE-complete? NP contains NP-complete problems and so does PSPACE. Am I supposed to prove it the same way as I would prove an NP-complete problem?

  • 2
    $\begingroup$ Not really. ​ ​ ​ Do you know the definition of ​ PSPACE - complete ? ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user12859 Nov 2 '16 at 22:35

For any complexity class $X$, a language is $X$-complete if it's in $X$ and every problem in $X$ can be reduced to it. There are two main ways to prove that a language is $X$-complete: literally show that it meets the definition of $X$-completeness, or show that some other $X$-complete problem reduces to it.

In cases where the language is essentially, "Here's a machine in~$X$ and an input: does it accept?", it's usually best to go for the literal approach and show that every problem in the class can be reduced to your problem. Why? Because every problem in the class is decided by a Turing machine, and your language is about whether those Turing machines accept or not.

| cite | improve this answer | |

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.