In "Computational Complexity" by Arora and Barak they state that the following is $NP$-complete:

$\{ \langle \alpha, x, 1^n , 1^t \rangle : \exists u \in \{0,1\}^n \text{ s.t. } M_{\alpha} \text{ outputs } 1 \text{ on input } \langle x,u \rangle, \text{ within } t \text{ steps} \}$.

They call this language $TSAT$.

I am trying to check the "complete" part of the claim.

Suppose $L \in NP.$ By definition, there is a polynomial $p$ and poly-time TM $M$ such that $\forall x \in \{0,1\}^*,$ we have $$x \in L \iff \exists u \in \{0,1\}^{p(|x|)} \text{ such that } M(x,u)=1.$$ Let $t()$ be the polynomial in which $M$ runs, and let $\alpha$ be the TM $M$ represented as a binary string. Then I think this mapping reduction $f$ works: $$f(x) = \langle \alpha, x, 1^{p(|x|)}, 1^{t(|x|)} \rangle.$$

My two questions are:

1) Is this correct?

2) If it's correct, how do we know that $f$ is computable? Just because some verifier $M$ exists, how do we guarantee that $f$ can "compute" it? Or is $M$ "hardcoded" in the Turing machine that is used to compute $f(x)$ from $x$?

  • $\begingroup$ 1) Yes. 2) $\alpha$ is hardcoded. $\endgroup$
    – dave
    Aug 29, 2018 at 18:07
  • $\begingroup$ Is the reason for including $1^t$ and requiring $M$ to run in $t$ steps simply to guarantee that $TSAT$ is indeed in $NP$? Or is it necessary for the reduction to work as well? $\endgroup$
    – theQman
    Aug 29, 2018 at 20:20
  • $\begingroup$ It is to guarantee that TSAT is indeed in NP. Without the requirement, the problem is not solvable by a Turing matching (i.e., $\not \in R$) $\endgroup$ Aug 29, 2018 at 21:53
  • $\begingroup$ If $t$ was given, as, say, the binary representation of $t$ (and not as $1^t$) the problem would be EXPTIME-complete. Including $1^t$ artifically blows up the input size, ensuring that $O(t)$ time is still polynomial in the input size (but note that $O(t)$ is exponential in the size of the binary representation of $t$). This is called padding. $\endgroup$ Aug 31, 2018 at 7:59

1 Answer 1


It's not correct. As you said, you cannot prove $f$ is polynomial-time computable.

However, you can reduce from a particular NP-complete language, for example, 3SAT. Now $f$ is polynomial-time computable as you can easily write a verifier for 3SAT.

  • $\begingroup$ I wouldn't say $f$ is not (poly-time) computable. $f$ simply isn't a function of $L$ (and couldn't be, because there is no way to represent $L$ as input to a Turing machine). $\endgroup$ Aug 31, 2018 at 8:00
  • $\begingroup$ @TomvanderZanden The input of $f$ is a string $x\in\{0,1\}^*$, which is clear in OP. Maybe using the notation $f_L$ instead of $f$ is more clear. $\endgroup$
    – xskxzr
    Aug 31, 2018 at 8:18

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.