I'm trying to prove that the language SPACE TMSAT (where SPACE TMSAT = {⟨$M$, $w$, $1^n$⟩ : DTM $M$ accepts $w$ in space $n$}) is PSPACE-complete.

My solution is as follows:
SPACE TMSAT $= \{<M,w,1^{n}> :$ DTM $M$ accepts $w$ in space $n\}$ can only be computed by running machine $M$ on $w$. As this forces the allowance of the computation of any PSPACE language, SPACE TMSAT is PSPACE-complete.

Does this solution make sense? Am I being too hand wavy? Any other suggestions or critiques? Thanks!


closed as off-topic by D.W., Realz Slaw, Luke Mathieson, Juho, frafl Nov 10 '13 at 16:59

  • This question does not appear to be about computer science within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 6
    $\begingroup$ This question appears to be off-topic because questions of the form: "This is the exercises problem, this is my solution. Please grade!" are not a good fit for this site. Please see this related meta discussion. If you want to ask a specific question about a specific part of your attempt, please edit the question accordingly. $\endgroup$ – D.W. Nov 4 '13 at 4:14
  • $\begingroup$ Besides, your solution is not good... Try to prove that your language is in PSPACE, i.e. describe precisely the machine that trecognize it (it has to stop on every input !). $\endgroup$ – Denis Nov 4 '13 at 11:07
  • 1
    $\begingroup$ @D.W. This is better than someone stating a question without any attempts at answering it. $\endgroup$ – Yuval Filmus Nov 6 '13 at 8:50

To prove that a problem $P$ is PSPACE-complete, you need to do two things:

  1. Show that $P$ can be computed in PSPACE.
  2. Show that every problem $Q \in $PSPACE reduces to $P$, in the sense that there exists a polytime function $f$ such that $f(x) \in P$ iff $x \in Q$.

As mentioned by dkuper, you forgot about the first part. Your argument for the second part (PSPACE-hardness) unfortunately does not constitute a proof. You need to follow the definition: given an arbitrary $Q \in $PSPACE, produce a polytime function $f$ such that $f(x) \in P$ iff $x \in Q$.

Apart from not being a proof, your argument is also not convincing: there could be some trick that avoids simulating $M$. Such tricks are behind results such as L=SL or NL=coNL in complexity theory. For example, the second result states that given a non-deterministic Turing machine $M$ that runs in logarithmic space, there is a ways to decide non-deterministically in logarithmic space whether a given input is not accepted by $M$. The obvious way to do this is to run all possible execution paths of $M$, but since $M$ could make polynomially many non-deterministic decisions, that would require polynomial space (we need to keep track of all these decisions so that we can run through all of them). Yet there is a trick that enables us to do it non-deterministically using only logarithmic space.

Hint for the second part: Given $Q$, consider a Turing machine $M$ that computes $Q$ in space $O(n^k)$ for some $k$.


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