Proving that $\mathrm{SpaceTMSat}$ is PSPACE-complete - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-22T03:18:05Z https://cs.stackexchange.com/feeds/question/65457 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/65457 0 Proving that $\mathrm{SpaceTMSat}$ is PSPACE-complete user60803 https://cs.stackexchange.com/users/60803 2016-11-02T21:57:22Z 2016-11-03T08:57:52Z <p>Let $\mathrm{SpaceTMSat} = \{\langle M, w, 1^n\rangle\mid\text {DTM$M$accepts$w$in space }n\}$.</p> <p>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?</p> https://cs.stackexchange.com/questions/65457/-/65482#65482 1 Answer by David Richerby for Proving that $\mathrm{SpaceTMSat}$ is PSPACE-complete David Richerby https://cs.stackexchange.com/users/9550 2016-11-03T08:57:52Z 2016-11-03T08:57:52Z <p>For any complexity class $X$, a language is $X$-complete if it's in&nbsp;$X$ and every problem in&nbsp;$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.</p> <p>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.</p>