A several equivalent NP definitions

Question

There are two definitions of NP I found:

1) NP is a set of problems that have poly-size certificates, and with a given input, there is a poly-time certifier that checks the proposed solution.

2) NP is a set of problems that can be solved by non-deterministic algorithm in polynomial time.

I think (1) is a standard definition that appears everywhere, but I found (2) from one of the lecture videos, but to the best of my knowledge, I think the reason why they're equivalent is that, a non-deterministic algorithm can make a lucky guess out of polynomially many options in constant time, and a result of these guesses would be our certificate.

But why (2) is restricted to guess one out of polynomially many options? Why can't it guess one out of exponentially many options? I don't have any knowledge about how non-deterministic algorithm or turing machine works.

Answer 1

The standard definition you'll usually find is the second one, but it makes no difference since they're indeed equivalent, and you can prove both arrows, I'll give a sketch of proof:

To see that (1) $\Rightarrow$ (2), consider a machine that non-deterministically guesses a certificate and then acts as a poly-time certifier.

On the other hand, to see (2) $\Rightarrow$ (1), observe that if a nondeterministic Turing machine decides $x \in L$ in polynomial time, then the set of nondeterministic choices it made in the path towards the accepting state is a certificate for $x$, and it must have polynomial size because by hypothesis every branch of the computation must terminate in polynomial time.

As for your second question, it is not true that a nondeterministic Turing machine can only guess out of polynomially many options (if it were the case, it could be simulated by a polynomially related deterministic machine). The limitation is that every computational branch must terminate in polynomial time. For instance, consider a nondeterministic machine for $\textsf{SAT}$: the number of valuations is exponential in the number of variables.

The reason why we give the characterization you cite in (1) is that we want to prove that $\textsf{NP}$ is the class of problems for which you can "guess" a solution and verify it in polynomial time, but a certificate that is more than polynomial in size cannot be "guessed" in polynomial time.

Answer 2

In fact a NTM can make a lucky guess out of constant possible many options in constant time. But each branch of computation takes polynomial time when it comes to the definition of the NP class. This is a post related to how a NTM works.