News for hackers. Stuff that matters.
Re:Jun Fukuyama's P≠NP Page by tbmbob on Monday December 10, 2012 @07:50PM (#4902511)
"If you need extra data to prove this "yes" in polynomial time, then the answer isn't a boolean anymore, but a boolean plus the extra data, so how can you still call that a yes/no problem?"

You are combining two distinct concepts: the answer and the 'evidence'. The answer to an NP-complete problem is always Yes or No. But, we say that we can "verify" a decision problem in polynomial time if, given an answer AND evidence, we can check that the answer is true.

For concreteness: the k-clique problem (determining if there's a clique of at least size k in a graph) is hard. But, if somebody told us the answer was Yes, and gave us appropriate evidence (say, a set of k nodes in the graph which form a clique), verifying would be easy.

There are no comments on this comment yet.