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

Question

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

Answer 1

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