Talk:Co-NP

From Wikipedia, the free encyclopedia

You have new messages (last change).

"This can be shown as follows. Assume that there is an NP-complete problem that is in co-NP. Since all problems in NP can be reduced to this problem it follows that for all problems in NP we can construct a non-deterministic Turing machine that decides the complement of the problem in polynomial time, i.e., NP is a subset of co-NP. From this it follows that the set of complements of the problems in NP is a subset of the set of complements of the problems in co-NP, i.e., co-NP is a subset of NP. Since we already knew that NP is a subset of co-NP it follows that they are the same. The proof for the fact that no co-NP-complete problem can be in NP is symmetrical."

The so called explanation above is unfortunately typical of what one finds on the web: unsubstantiated claims. "Since all problems in NP can be reduced to this problem it follows that...", sure it is easy to make this *claim*, but WHY does it follow that...?

Then, more of the same: "From this it follows that the set of complements...", well, WHY does it follow?

The explanation is useless, because it merely makes unsubstantiated assertions.

well this article must be a bit older. Primes is in P!

Personally I think it pretty unreasonable to expect an article on higher mathematics to explain every step of a proof in excruciating detail. Some ability on the part of the reader is to be expected. And Primes is certainly in P, but Integer Factorization is a different problem, as the linked article explains in detail.

The claims of the article follow immediately from the definitions of NP-complete, NP, and reducibility. That said, this result is so obvious that I'm not sure it even deserves all this space, since it will be obvious for people who know what's going on and confusing for those who don't. --Saforrest 21:23, 4 November 2005 (UTC)

NP and co-NP are also thought to be unequal.

Does this mean "not equal", or does it mean "disjunct"? --zeno 10:25, 17 Nov 2004 (UTC)

It means "not equal". Think for example of P which is non-empty and a subset of both, so clearly their intersection cannot be empty. -- Jan Hidders 17:44, 17 Nov 2004 (UTC)

Got it. Must have been drunk when asking that stupid question ;-). --zeno 16:37, 25 Jun 2005 (UTC)

[edit] counterexamples

"In simple terms, co-NP is the class of problems for which efficiently verifiable proofs of no instances, sometimes called counterexamples, exist."

If a problem is in co-NP, its complement is in NP. Of course, there are problems in NP that are hard. Why is it efficient to verify if a counterexample for a co-NP exists?

[edit] Subset sum counterexample

"Its complement problem is in co-NP and asks if every subset sums to a nonzero number. A counterexample would be a subset which does sum to zero, which is easy to verify."

I think a trivial counterexample would be the empty subset for any instance of the complement problem (depending on the "sum" of the empty subset of course, but it is reasonable to assume that the sum of the empty subset is zero). Maybe we should be more specific and point out that we talk about non-empty subsets here. Any objections? --Tamas Nepusz 12:54, 28 February 2006 (UTC)

No; No one can object to mathematics. --ANONYMOUS COWARD0xC0DE 05:38, 1 December 2006 (UTC)

Retrieved from "http://en.wikipedia.org../../../c/o/-/Talk%7ECo-NP_2449.html"