1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael♦ Nov 18 '17 at 22:08
4
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I think you misunderstood the guessing. For example 3-SAT problem, we consider a variable and guess whether it's going to be true or false. We make such guesses for every variable $\endgroup$ – Ted Nov 18 '17 at 0:42
  • $\begingroup$ But technically I'm guessing a solution $\endgroup$ – Ted Nov 18 '17 at 0:44
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.