P might be NP: A Polynomial Time Algorithm for the Hamilton Circuit Problem
1–10 of 48 posts
Re: P might be NP: A Polynomial Time Algorithm for the Hamilton Circuit Problem
#2Just 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.
To solve the MSP problem, we propose a polynomial algorithm ...
... and prove its NP-completeness.
They use the word "its" - to what are they referring? The algorithm? That doesn't make sense, as an algorithm is not something that's NPC. The MSP problem? Earlier claimed results show that it's NP-Hard, now they're showing it's P, so to "prove its NP-completeness" doesn't fit.
However, English is not their first language (I assume) so perhaps I'm over-thinking irrelevant detail.
Our result implies NP=P.
Now I'm off to see if I, as a non-specialist, can make any sense of it.
Re: P might be NP: A Polynomial Time Algorithm for the Hamilton Circuit Problem
#3Just 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…
Further into the article they state
"This paper persents the full version of our idea to solve this famous problem. We will introduce a so-called 'Multistage graph Simple Path' (MSP) problem and prove its NP-completeness. To solve the MSP problem, we will propose a polynomial algorithm and prove its correctness."
Re: P might be NP: A Polynomial Time Algorithm for the Hamilton Circuit Problem
#4ArXiv 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.
Re: P might be NP: A Polynomial Time Algorithm for the Hamilton Circuit Problem
#5Just 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…
From the Introduction:
We will introduce a so-called 'Multistage graph Simple
Path' (MSP) problem and prove its NP-completeness.
Re: P might be NP: A Polynomial Time Algorithm for the Hamilton Circuit Problem
#6Just 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…
From the Introduction: We will introduce a so-called 'Multistage graph Simple Path' (MSP) problem and prove its NP-completeness. So what they claim to be NP-complete is their new problem and not the algorithm as it should be. I'll still say this will turn out to not be real. I won't even try to follow their paper but it's not written in LaTeX so it can't be real math... :)
They claim to have a new problem (MSP) which is NP-Hard because HC reduces to it, and they claim to have a polynomial algorithm to solve MSP.
That's all very reasonable. What's less reasonable is that all of the references bar one are to their own papers, and a paper from 2010 claims to have been presented at a conference, and to prove this result.
It's not passing the sniff test, but I'll still see if the first few pages make sense.
Re: P might be NP: A Polynomial Time Algorithm for the Hamilton Circuit Problem
#7ArXiv 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.
Re: P might be NP: A Polynomial Time Algorithm for the Hamilton Circuit Problem
#8From 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.
Re: P might be NP: A Polynomial Time Algorithm for the Hamilton Circuit Problem
#9the arxiv doesn't peer-review papers. it has lots of proofs of famous conjectures, et cetera.
this paper, in particular, smells fishy. the author doesn't cite anyone but himself for significant result (he does cite someone else for referencing material that's standard for specialists.)
Re: P might be NP: A Polynomial Time Algorithm for the Hamilton Circuit Problem
#10From 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/
In this case, I think it shows uncommon good sense. There have been how many claims that P=NP?
Ironically, the author being this careful makes me think he's more likely to be right.