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

Improve this question
$\endgroup$
4
  • $\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$
    – user3563894
    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$
    – Tom van der Zanden
    Aug 31, 2018 at 7:59

1 Answer 1

Reset to default
1
$\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.

Improve this answer
$\endgroup$
2
  • $\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, 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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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