If you want to make money online : Register now

[Solved]: If NP is the class of problems that cannot be solved in polynomial time, what is co-NP?

, , No Comments
Problem Detail: 

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?

Asked By : Beached Whale

Answered By : gnasher729

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/65969

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback