NP = coNP(arxiv.org)

4 pointsby tantalor11 lat temu2 comments

http://arxiv.org/abs/1506.00095

2 comments

mdxn11 lat temu

I heavily suspect this claim is wrong due to some amateurish mistakes. In particular, I believe the author is confusing the concepts of "checking" a solution and "searching" for one. At some points in the paper, their use of the word "detecting" (an ESS) is equivalent to "checking", but the logic of the argument (very simple, might I add) seems to equivocate it to "searching for" an ESS. The distinction between these two tasks is exactly the distinction between P and NP. So I'm inclined to blame this on lack of reading comprehension on the author's part when piecing together information from other works.

Assuming that the author wasn't inconsistent in the meaning of the term "detection", then they are probably claiming that there is some sort of polynomial time reduction taking place between recognizing a solution to an ESS problem (coNP-complete) and recognizing a strict local maximum in a quadratic program (NP-hard according to the author). I don't see this explicitly done in the paper and doubt what they have yields one even if I had more of the context. Unfortunately, I wasn't able to evaluate all of the citations since they are behind paywalls. I wish there was enough information in the actual paper to determine this.

yzh11 lat temu

So I read this post afterwards: http://cs.stackexchange.com/questions/9795/is-the-open-quest... Then I know why this proof is important. Hope it can get through some peer-reviewed journal/conference later.