# $TSAT$ is $NP$-complete

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

• 1) Yes. 2) $\alpha$ is hardcoded.
– dave
Aug 29 '18 at 18:07
• 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? Aug 29 '18 at 20:20
• 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$) Aug 29 '18 at 21:53
• 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. Aug 31 '18 at 7:59

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.
• 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). Aug 31 '18 at 8:00
• @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. Aug 31 '18 at 8:18