# Providing $1^n$ as input to protect against degenerate cases

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

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$.
• "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)$? – theQman Dec 12 '16 at 20:14
• 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. – Yuval Filmus Dec 12 '16 at 20:16