1
$\begingroup$

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!

$\endgroup$
  • 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
2
$\begingroup$

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$.

$\endgroup$

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