Two definitions of coNP

Question

If $L\subseteq \{0, 1\}^∗$ is a language, then we denote by $\overline{L}$ the complement of $L$. That is, $\overline{L} = \{0, 1\}^∗\setminus L.$ We make the following one definition of $\mathrm{coNP}$: $$\mathrm{coNP} = \{L : \overline{L} ∈ \mathrm{NP}\}.$$

$\mathrm{coNP}$, ALTERNATIVE DEFINITION:

For every $L\subseteq \{0, 1\}^∗$, we say that $L\in \mathrm{coNP}$ if there exists a polynomial $p \colon \mathbb{N}\to \mathbb{N}$ and a polynomial-time TM $M$ such that for every $x\in \{0, 1\}^∗$, $$x\in L \iff \forall u \in \{0, 1\}^{p(|x|)}\: M(x, u) = 1.$$

I am not able to understand why and how both two definitions are equivalent; the book mentions these two but does not say anything about the equivalence.

Answer 1

We should prove that the former implies the latter definition and vice versa.

Let $\mathbf{coNP}=\{L:\overline{L}\in\mathbf{NP}\}$. For $L\in\mathbf{coNP}$, there exists a polynomial $p(n)$ and a polynomial-time TM $M$ such that for every $$x\in\overline{L}\iff\exists u\in\{0,1\}^{p(n)}\;M(x,u)=1$$ because $\overline{L}\in\mathbf{NP}$. Thus, $$x\in L\iff\forall u\in\{0,1\}^{p(n)}\;M(x,u)=0.$$ We additionally construct a polynomial-time deterministic TM $M'$ s.t. $M'(x)=1-M(x), \forall x\in\{0,1\}^*$. We finally have $L\in\mathbf{coNP}$, there exists a polynomial $p(n)$ and a polynomial-time TM $M'$ such that for every $$x\in L\iff\forall u\in\{0,1\}^{p(n)}\;M'(x,u)=1.$$

The other, i.e. the latter implies the former, is similar.