0

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?

Asaf Karagila
  • 393,674
jri
  • 109
  • It might help to imagine an element of N as a pair of an element of M together with a choice of coinflips. We could then use those coinflips to "determinize" a non deterministic TM. – daniel gratzer Apr 24 '21 at 16:35
  • I agree with @DanielGratzer except that I'd avoid the word "coinflip" when dealing with nondeterministic (rather than randomizing) algorithms. Alternatively, you could think of the second component $y$ of a pair $\langle x,y\rangle\in N$ as the entire record of an accepting run of your NDTM on input $x$. (By the way, some authors use statement 2 in the question as the definition of NP.) – Andreas Blass Apr 24 '21 at 17:26

0 Answers0