Proof of an alternative description of NP by a lemma

30 Views Asked by At

Consider the this lemma: The following two statements are equivalent for every set of M.

  1. $M \in NP$
  2. there is a $N \in P$ and a polynomial q, that $M = \{x \vert \exists y, \vert y \vert \le q(\vert x \vert) : <x,y> \in N\}$ (where $\vert x \vert$ is the length of the word x)

How can one proof that this Lemma is true?