Talk:co-NP

Untitled

"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)[reply]

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)

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?

I think you got confused by the wording. What it means is there exists an efficient algorithm to verify a counter-example. Olivier / 20:51, 27 February 2007 (UTC)

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)[reply]

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

small correction

"Primality testing was thought to be in NP and co-NP, just as factorization is, until the AKS primality test showed in 2002 that it is in P."

This makes it sound like we no longer think primality testing is in NP and co-NP. However, since it is in P, isn't it by definition still in NP and co-NP? In other words, wouldn't a better statement be, "Primality testing was thought to be strictly in NP and co-NP, just as factorization is, until the AKS primality test showed in 2002 that it is also in P."?

Your wording implies that factorization is not in P, which isn't known. I will clarify it. Dcoetzee 00:24, 24 July 2007 (UTC)[reply]

"Membership in co-NP is more subtle; one must list the prime factors of m and provide a primality certificate for each one."

Doesn't the AKS test also eliminate the need for the primality cert? —Preceding unsigned comment added by 131.107.0.86 (talk) 19:22, 14 September 2009 (UTC)[reply]

Yes, it does now. It's still useful to know that you don't have to rely on the AKS test for this. --Robin (talk) 02:16, 15 September 2009 (UTC)[reply]

Bolding

The excessive bolding of names of complexity classes is quite distracting, and I find it makes the article hard to read. Why are these bolded? Is there any style policy/trend on the subject? ~ Booya ^Bazooka 16:17, 7 April 2008 (UTC)[reply]

Because they're names of math things, like R is by agreement the real line. --149.4.211.210 (talk) 18:51, 12 September 2008 (UTC)[reply]

Integer Factorization membership in co-NP

" Membership in co-NP is also straightforward: one can just list the prime factors of m, all greater or equal to n, which the verifier can confirm to be valid by multiplication and the AKS primality test."

This is either not straightforward (to me) or the wording is odd.

To prove (Given m,n ∃ 1<x<n: x | m )? is in co-NP
is equivalent to prove ¬(Given m,n ∃ 1<x<n: x | m)? is in NP
which is equivalent to prove (Given m,n ∀ 1<x<n: ¬(x | m))? is in NP

So then the current proof is saying that if you find that all prime factors of m are greater than or equal n, then m must have no factor that are less than n? In the current proof, it seems given that all factors are greater than or equal to n, not something that is tested. Nicksoccer03 (talk) 21:10, 18 February 2018 (UTC)[reply]

Claims about NP = co-NP = PSPACE

The cited paper^[1] claims to have solved multiple unsolved problems in computer science. This is gonna need far more citations from reliable third-party reviews. --Ebf526 (talk) 23:23, 27 November 2020 (UTC)[reply]

Full reference: ^[2]. I've removed it for now because its claims are dubious. Despite being a peer-reviewed work, NP and coNP are thought unequal, as are NP/coNP and PSPACE, and the field is well-known for frequent claims of proofs or disproofs of open problems which do not work. The consequences (e.g. polynomial hierarchy collapse) are sufficiently drastic that this proof needs a lot more evidence of widespread academic acceptance before it's worth mentioning. — Bilorv (talk) 10:18, 28 November 2020 (UTC)[reply]

References

^ https://czasopisma.uni.lodz.pl/bulletin/article/view/8169
^ Gordeev, Lew; Haeusler, Edward Hermann (2020-08-15). "Proof Compression and NP Versus PSPACE II". Bulletin of the Section of Logic. doi:10.18778/0138-0680.2020.16. ISSN 2449-836X.

[1] ttps://czasopisma.uni.lodz.pl/bulletin/article/view/8169

[2] Gordeev, Lew; Haeusler, Edward Hermann (2020-08-15). "Proof Compression and NP Versus PSPACE II". Bulletin of the Section of Logic. doi:10.18778/0138-0680.2020.16. ISSN 2449-836X.

[1]

[2]