Re:Jun Fukuyama's P≠NP Page
by btilly on Monday December 10, 2012 @07:39PM
(#4902466)
...if you can verify a boolean answer in polynomial time, you can always find the solution in polynomial time too, after all there are only two possible solutions so you need to verify only one to find the answer.
It doesn't work that way. The common characteristic of NP-complete problems is that there are an exponential number of possible solutions, but verifying that a purported solution is a solution takes only polynomial time.
For example consider SAT (see http://en.wikipedia.org/wiki/Boolean_satisfiability_problem for more). This is the problem of deciding whether there is a set of possible variable values that make a given Boolean equation evaluate to True. For an equation of length n there are in general O(n) variables, and therefore 2^O(n) possible sets of true/false values that the variables can have. So a brute force search takes exponential time.
But if you give me an equation, AND a set of values for the variables that you claim will result in the final expression evaluating to True, I can verify it in time O(n).
It doesn't work that way. The common characteristic of NP-complete problems is that there are an exponential number of possible solutions, but verifying that a purported solution is a solution takes only polynomial time.
For example consider SAT (see http://en.wikipedia.org/wiki/Boolean_satisfiability_problem for more). This is the problem of deciding whether there is a set of possible variable values that make a given Boolean equation evaluate to True. For an equation of length n there are in general O(n) variables, and therefore 2^O(n) possible sets of true/false values that the variables can have. So a brute force search takes exponential time.
But if you give me an equation, AND a set of values for the variables that you claim will result in the final expression evaluating to True, I can verify it in time O(n).
Does that answer your question?