0
$\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?

Improve this question
$\endgroup$
3
  • 7
    $\begingroup$ Your professor has no idea what they are talking about. Find better resources such as textbooks; we also have some reference material. $\endgroup$
    – Raphael ♦
    Nov 13, 2016 at 9:03
  • 6
    $\begingroup$ Community votes, please: duplicate? $\endgroup$
    – Raphael ♦
    Nov 13, 2016 at 9:04
  • 3
    $\begingroup$ If NP is the class of problems that cannot be solved in polynomial time then co-NP is a banana. en.wikipedia.org/wiki/Vacuous_truth $\endgroup$
    – Reinstate Monica
    Nov 14, 2016 at 17:08

1 Answer 1

Reset to default
12
$\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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Hint = Certificate? $\endgroup$
    – Fraïssé
    Nov 14, 2016 at 18:46
  • 1
    $\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, 2016 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, 2016 at 9:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.