3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 1) Yes. 2) $\alpha$ is hardcoded. $\endgroup$ – dave Aug 29 '18 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 '18 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$ – user3563894 Aug 29 '18 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$ – Tom van der Zanden Aug 31 '18 at 7:59
0
$\begingroup$

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.

$\endgroup$
  • $\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$ – Tom van der Zanden Aug 31 '18 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 '18 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.