If you scroll to the last page, you'll find that this "Xinwen Jiang" character cites: a textbook on computational complexity from the '70s, plus himself (in the apparently nonexistent Computer Technology and Automation), more than ten times. Furthermore, he's been at this since 1993. A dedicated crank if I've ever seen one.
P might be NP: A Polynomial Time Algorithm for the Hamilton Circuit Problem
11–20 of 48 posts
Re: P might be NP: A Polynomial Time Algorithm for the Hamilton Circuit Problem
#12I'm very skeptical, for the following reasons:
1. The author first released this paper (well, a version of it) in April 2009. It seems unlikely that it would have gone unnoticed for four years if the proof was valid.
2. Aside from a 1979 textbook and a 2010 paper, the author only cites himself (10 times!)
3. The author does not use TeX (see 1. at "Ten Signs A Claimed Mathematical Breakthrough is False" http://www.scottaaronson.com/blog/?p=304)
Re: P might be NP: A Polynomial Time Algorithm for the Hamilton Circuit Problem
#13From the author home page: 'It seems our algorithm is a polynomial one. So we would like to discuss with more people.' It's weird if a proof doesn't even convince the author. https://sites.google.com/site/xinwenjiang/
I'm not a specialist by any means, but he also ends the paper "All the results show that our polynomial time algorithm can get the same answer as the backtracking algorithm does. No exception.", which doesn't seem to imply a concrete proof.
Re: P might be NP: A Polynomial Time Algorithm for the Hamilton Circuit Problem
#14Yes, not looking good
It will certainly be amazing if it is true, but it doesn't look right
The style, the constructs in the article, etc
But yes, translating one NP problem to another NP problem is a n allowed approach and has been done between several NP problems (if you prove your translation is correct, and valid all the time, of course)
Re: P might be NP: A Polynomial Time Algorithm for the Hamilton Circuit Problem
#15ArXiv has many "proofs" that P=NP and that P!=NP. ArXiv does not do any vetting of correctness (it is beyond their scope.) We don't need a HN submission for this and the title is inaccurate/clickbait.
"Please don't submit comments complaining that a submission is inappropriate for the site." http://ycombinator.com/newsguidelines.html People have upvoted this article, therefore there should have been a submission for it.
Fair enough, but people should know that arXiv does not have a crackpot filter (this is not a bad thing. ArXiv is excellent!) Any random pdf claiming to decide P = NP on the internet is going to be crackpot stuff.
(Off topic) My favourite silly arXiv post is this one, mostly for the dramatic title and abstract: http://arxiv.org/abs/0809.4144
Re: P might be NP: A Polynomial Time Algorithm for the Hamilton Circuit Problem
#16From the author home page: 'It seems our algorithm is a polynomial one. So we would like to discuss with more people.' It's weird if a proof doesn't even convince the author. https://sites.google.com/site/xinwenjiang/
"Beware of bugs in the above code; I have only proved it correct, not tried it." - Donald Knuth
Re: P might be NP: A Polynomial Time Algorithm for the Hamilton Circuit Problem
#17ArXiv has many "proofs" that P=NP and that P!=NP. ArXiv does not do any vetting of correctness (it is beyond their scope.) We don't need a HN submission for this and the title is inaccurate/clickbait.
I wonder why authors of P=NP 'proofs' won't attach a program that solves some NP hard problem for a collection of large inputs in reasonable time.
This of course wouldn't prove the work is valid, but should be enough to draw attention and have the paper reviewed by qualified people.
Re: P might be NP: A Polynomial Time Algorithm for the Hamilton Circuit Problem
#18ArXiv has many "proofs" that P=NP and that P!=NP. ArXiv does not do any vetting of correctness (it is beyond their scope.) We don't need a HN submission for this and the title is inaccurate/clickbait.
I wonder why authors of P=NP 'proofs' won't attach a program that solves some NP hard problem for a collection of large inputs in reasonable time. This of course wouldn't prove the work is valid, but should be enough to draw attention and have the paper reviewed by qualified people.
O(n^10) algorithm is in P, but does not solve large inputs in reasonable time.
Re: P might be NP: A Polynomial Time Algorithm for the Hamilton Circuit Problem
#19ArXiv has many "proofs" that P=NP and that P!=NP. ArXiv does not do any vetting of correctness (it is beyond their scope.) We don't need a HN submission for this and the title is inaccurate/clickbait.
I wonder why authors of P=NP 'proofs' won't attach a program that solves some NP hard problem for a collection of large inputs in reasonable time. This of course wouldn't prove the work is valid, but should be enough to draw attention and have the paper reviewed by qualified people.
That's a good question, but always keep in mind that polynomial time doesn't imply that it'll be faster than the currently used algorithms on any real application.
Re: P might be NP: A Polynomial Time Algorithm for the Hamilton Circuit Problem
#20Just looking at the abstract: In this paper, we introduce a so-called Multistage graph Simple Path (MSP) problem and show that the Hamilton Circuit (HC) problem can be polynomially reducible to the MSP problem. That would imply that the MSP is NP-hard. So far, so good. To solve the MSP problem, we propose a polynomial algorithm ... That would imply that P=NP, and hence this would be a major result, with potentially w…
> Pause. This doesn't make sense. If you have a polynomial algorithm then it's in P. If you've reduced HC to MSP then you've already shown MSP is NP-Hard.
This actually makes sense, although it wouldn't be necessary to point out.
If the author proves that P=NP, then all problems in P are NP-complete (because every problem in P is reducible to any non-trivial problem in P).
The paper doesn't look very promising to me, but the basic logic of the argument makes sense.