1
$\begingroup$

In my super non-rigorous class on optimization, the prof defined NP as the class of decision problems that cannot be solved in polynomial time. By definition, P is the class of decision problems that can be solved in polynomial time.

Then what is so called co-NP? Does co-NP = P in the sense of 'complement' of a set as used in set point topology?

Is there an intuitive way of explaining the meaning of co-NP in terms of problem that can be solved in _________ time? And the intersection between NP and co-NP?

$\endgroup$
11
$\begingroup$

Your prof was absolutely not rigorous (i.e. completely wrong), that's why the distinction between NP and co-NP doesn't make sense with his definition. Better definition:

Def.: A decision problem (that is a problem where the result is either YES or NO and nothing else) is in NP if for every instance where the result is YES there exists a hint such that we can prove that the result is YES in polynomial time in the size of the problem by using the hint. (You will notice that there need not be a hint to prove the answer is NO, if the answer is indeed NO).

An example (not NP complete): If your decision problem is whether a number is composite (YES) or prime (NO), then for every composite number I can give you as a hint one non-trivial factor f. Then you can prove that the answer is YES by checking that the number is divisible by f.

Interestingly, when the number is prime, there isn't such a trivial hint that let's you prove the answer is NO. (There are hints, but nowhere near as simple).

And co-NP is defined almost the same, except there must be a hint if the answer is NO. For every problem X in NP, you can pose the problem Y: "Is the answer to problem X NO", and that problem Y would be in co-NP by definition.

$\endgroup$
  • $\begingroup$ Hint = Certificate? $\endgroup$ – Carlos - the Mongoose - Danger Nov 14 '16 at 18:46
  • $\begingroup$ "Certificate" is just more formal. There are alternative ways to describe NP: My favourite is "can solve in linear time if you are capable of making lucky guesses". For example: Is x composite? Solution: Make a lucky guess to get a factor f of x. Check that x is divisible by f. $\endgroup$ – gnasher729 Nov 14 '16 at 21:36
  • $\begingroup$ Or to solve the travelling salesman problem: Can I visit all 50 capitols of the USA in a trip of less than 3,000 miles? Solution: Make lucky guesses where to start, which capitol to go to first, which capitol after that etc., and check that this tour meets the rules and is less than 3,000 miles. $\endgroup$ – gnasher729 Nov 15 '16 at 9:49

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.