0
$\begingroup$

To show $\text{PSPACE-completeness}$ of $\text{SPACE-TMSAT}$, we perform a polynomial-time reduction of $\forall L \in \text{PSPACE}$ to $\text{SPACE-TMSAT}$. The language $L$ can be decided by a TM $M$ that takes at most $O(n^k)$ space for some constant $k > 0$. Does the reduction require the value of this constant $k$?

I feel the reduction makes an inherent assumption of the value $k$, I am not sure if this value is required. If the value is required then how do we calculate this?

Edit: This solution hints towards the above reduction, but this minute detail is not clear to me.

Edit(2): Made the question more clear based on comment

$\endgroup$
1
  • $\begingroup$ What do you mean by a reduction of $L$? A reduction from $L$? to $L$? Where does the TM come from? The question is unclear. $\endgroup$ Feb 11 at 18:31

1 Answer 1

0
$\begingroup$

When we write $A\leq_p B$, we mean that there exists a polynomial-time reduction from $A$ to $B$, and we don't care whether you have a description of such reduction in hand. So we're trying to prove the existence of a reduction. If $k$ is a constant, then there exists machine that encodes this constant, and therefore one can use that machine to conclude the existence of a machine that computes the reduction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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