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