0

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

invictus
  • 81
  • 5
  • 2
    If you **already have** a solution, you can prove that it's right in polynomial time. **Finding** the solution in polynomial time is what P is. – Bernhard Barker May 29 '17 at 08:05
  • I know that is one part of NP. What I am curious about is the quote above. What does it mean by "a solution can be guessed out of polynomially many options in O(1) time"? – invictus May 29 '17 at 10:18
  • If the quote is correct, then it isn't talking about guessing a solution to a whole NP problem -- that would be guessing from exponentially many solutions in linear or polynomial time. Instead it would be talking about how big a guess you can make in O(1) "steps". Even then it's a little dodgy – Matt Timmermans May 29 '17 at 12:26
  • The "polynomially many options" bit seems just plain wrong to me. – nondeterministic Feb 26 '18 at 19:32

1 Answers1

6

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.

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138