This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
"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!
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)
Got it. Must have been drunk when asking that stupid question ;-). -- zeno 16:37, 25 Jun 2005 (UTC)
"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?
"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)
"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."?
"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)
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)
" 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.
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)
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)
References
This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
"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!
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)
Got it. Must have been drunk when asking that stupid question ;-). -- zeno 16:37, 25 Jun 2005 (UTC)
"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?
"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)
"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."?
"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)
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)
" 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.
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)
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)
References