I am studying NP-Completeness and I have a question about the definition of the NP problems.
Material says
nondeterministic refers to the fact that a solution can be guessed out of polynomially many options in O(1) time
Here, what does it mean by polynomially many options in O(1) time?
For example, in the case of famous 3SAT problem, isn't there a exponentially many options?
(b.c. each literal can be true or false and if there are are n literals, total number of options are 2*2*2* ... * 2 = 2^n)
However, it says 3SAT problem is NP problem. How can it be NP problem even though there are exponentionally many certificates?
Thanks
That quote seems to be a weird way of phrasing it, but it might refer to something similar to being able to pick a random number between 1 and n in O(1) - there are n possibilities, but only picking one of them takes O(1).
See also: nondeterministic algorithms.
"Nondeterministic polynomial time" is the full definition of NP - "polynomial time" is important - each decision you make might take O(1), but there are polynomially many such decisions, leading to something that can theoretically be solved in polynomial time, if you can make the right choice at every step or execute all options at the same time.
Picture a k-ary tree with height p(n). You can get to the correct leaf in O(p(n)) if you (randomly) pick the correct child at each step from the root, or if you can somehow visit all paths concurrently.
Of course, in practice, you can't rely on making correct random choices, nor do you have infinitely many processors - if you were to visit all nodes sequentially, that will take O(kp(n)).
For 3SAT, we can randomly pick true or false for every literal, which leads us to a polynomial time algorithm which would produce the correct result if all our random choices were correct.