2
$\begingroup$

The following language is NP-complete:

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

I would like to have a stronger understanding of the $1^n$ and $1^t$ inputs that are provided as auxiliary inputs. Is the above language equivalent to the following one?

$$\{ (\alpha, x, 1^t): \exists \text{ polynomial p and }u \in \{0,1\}^{p(t)} \text{ s.t. } M_\alpha \text{ outputs 1 on input } (x,u) \text{ within t steps}\}$$

I believe this gets around the technicality of allowing certificates that are sufficiently large, but not too large.

As for the $1^t$ input, what is the situation we are trying to protect ourselves against? Why isn't it sufficient to provide $(\alpha, x))$ as inputs and require that $M_\alpha$ run in time $p(|x|)$?

$\endgroup$
2
$\begingroup$

Your second language is (probably) not in NP, since it allows witnesses of arbitrary size. For every size $m$ there is a polynomial $p$ such that $p(t) = m$, for example the constant polynomial $p \equiv m$. A polynomial time machine should have its running time bounded by a fixed polynomial in the input size.

Regarding $t$, if you replaced the unary encoding of $t$ by its binary encoding then you would get a problem in NEXP rather than in NP, since simulating $t$ steps of a machine scales proportional to $t$, whereas the size of the binary encoding of $t$ is only $\log t$.

$\endgroup$
  • $\begingroup$ "A polynomial time machine should have its running time bounded by a fixed polynomial in the input size." I don't quite see how my second language violates this. Wont't the certificate still be of size polynomial in the input since $1^t$ is part of the input and the certificate is of length $p(t)$? $\endgroup$ – theQman Dec 12 '16 at 20:14
  • $\begingroup$ Your polynomial $p$ isn't fixed. That's the difference. In fact, it is completely meaningless, as I point out in the answer, since you can just choose $p$ to be an arbitrary constant polynomial. The concept of polynomial time only makes sense for growing input lengths. You cannot judge this from the running time on one particular input length. $\endgroup$ – Yuval Filmus Dec 12 '16 at 20:16

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.