6 ms·

P might be NP: A Polynomial Time Algorithm for the Hamilton Circuit Problem

44 points by Filligree 13y ago

ColinWright 13y ago
Just 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 wide-reaching consequences. ... and prove its NP-completeness. 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. 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. Yes, yes it would. Now I'm off to see if I, as a non-specialist, can make any sense of it.
- im3w1l 13y ago
  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."
- pedrocr 13y ago
  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... :)
  - ColinWright 13y ago
    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.
- jb17 13y ago
  > 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.
jacobparker 13y ago
ArXiv 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.
- quarterto 13y ago
  "Please don't submit comments complaining that a submission is inappropriate for the site." http://ycombinator.com/newsguidelines.html http://ycombinator.com/newsguidelines.html People have upvoted this article, therefore there should have been a submission for it.
  - jacobparker 13y ago
    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 http://arxiv.org/abs/0809.4144
- mixedbit 13y ago
  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.
  - dagw 13y ago
    Mathematically you can prove that an algorithm with certain properties exists, without being able to implement it. Also, as others have pointed out, polynomial does not necessarily mean "fast".
    - mixedbit 13y ago
      Interesting, are you aware of any such algorithm (proven to exist but not discovered yet)?
mixedbit 13y ago
From 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/ https://sites.google.com/site/xinwenjiang/
- Filligree 13y ago
  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.
- mcintyre1994 13y ago
  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.
- samolang 13y ago
  "Beware of bugs in the above code; I have only proved it correct, not tried it." - Donald Knuth
  - devrelm 13y ago
    This appears to be a corollary: "Beware of bugs in the above code; I have only tried it, not proved it correct."
mebassett 13y ago
the 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.) related: http://primes.utm.edu/notes/crackpot.html http://primes.utm.edu/notes/crackpot.html
scythe 13y ago
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.
- stiff 13y ago
  Spot the error or shut up. If Ramajuan would write a paper himself he could only cite some rather obscure mathematical encyclopedia, he still uncovered wide areas of mathematics unknown to his contemporaries. There might be one Ramajuan for 100 000 cranks, but it still sucks to dismiss someones work based on the fucking bibliography...
  - ColinWright 13y ago
    > Spot the error or shut up. That's not really how it works. I'm deciding whether it's worth my time trying to understand this. If it's really the breakthrough it purports to be, I can expect there to be some deep ideas and difficult tricks - I expect this to take both time and effort. To decide whether I'll bother I apply several heuristics, many of which are well-known and informally documented. If the first page or two just seems like obvious stuff, or is subtly nonsensical, then I won't bother. But I am certainly concerned that he doesn't cite any other significant work at all. More, the claims toward the end are rather, well, indistinct. It's doing very well against the ten heuristics in this blog post: http://www.scottaaronson.com/blog/?p=304 http://www.scottaaronson.com/blog/?p=304
    - raverbashing 13y ago
      Well, the best heuristic is finding a mistake, and if it's a crank there should be several.
      - ColinWright 13y ago
        It doesn't always work like that. Sometimes a paper is, after enough trying to understand what's going on, simply nonsense. It can be hard work wading through pages of unmotivated and apparently random definitions, trying to find some sense, only to have it completely fall apart. There aren't always obvious mistakes. Sometimes it makes sense locally, but not globally. Taking an early assessment can help enormously in avoiding time-wasters.
crntaylor 13y ago
I'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 http://www.scottaaronson.com/blog/?p=304)
- glomph 13y ago
  >At some point, there might be nothing left to do except to roll up your sleeves, brew some coffee, and tell your graduate student to read the paper and report back to you. Hahaha.
raverbashing 13y ago
Yes, 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)
stiff 13y ago
I spent some forty minutes on this, I think his "multistage graph simple path problem" is a very obfuscated version of a simpler problem where there is no need for this complicated labelling of vertices, with the information being instead reflected in the connections between vertices. I think the problem he discusses is simply the problem of determining whether two vertices in a graph are connected via a path or not. Did anyone else understand his problem formulation and had any similar impressions? I have a microscopic hope of this being a valid P=NP proof, still would be nice to know wtf is this about.
- ColinWright 13y ago
  His "Multistage Graph" seems poorly defined. I'm slowly coming to grasp what I think it is, but he defines is as G = <V,E,S,D,L> but pulls the E(v) from nowhere. It's not looking good.
  - stiff 13y ago
    Yes, I think the intention is for E(v) to be one of the inputs of the algorithm (I contemplated E(v) for half an hour to guess this is what he means). I thought maybe the following is possible: I create a new graph with the same vertices as his graph, but instead of having an E(v) I connect each vertex to the members of E(v) via an edge. Afterwards, if two vertices are not connected via an edge in his original graph, I remove this edge from my new graph. I cannot really get to the heart of it, I just had a vague impression this might be equivalent, either way I think the problem could likely be formalized in a more effective way.
- usamec 13y ago
  Nope, there are constrains on how the path might look or not. The constrains have form: Is path enters vertex v, then it might only use edges {...}.
  - ColinWright 13y ago
    Yes - it's getting harder and harder to pin down exactly what this problem really is, what an example of it is really like, and what's really going on. I'm sure the author has something in mind. I'm sure it's not well explained, and it might even prove insufficiently explained to be able to assess it properly. It's looking like it's locally "OK" but globally nonsense.
dburgoyne 13y ago
Jiang found a polynomial-time algorithm for solving what he calls "labelled multistage graphs" Note that these graphs are partially ordered sets (http://en.wikipedia.org/wiki/Partially_ordered_set http://en.wikipedia.org/wiki/Partially_ordered_set) and every partially ordered set has a unique corresponding comparability graph (http://en.wikipedia.org/wiki/Comparability_graph http://en.wikipedia.org/wiki/Comparability_graph) and the problem of finding a Hamiltonian cycle in a comparability graph is known not to be NP-complete. (http://link.springer.com/article/10.1007%2FBF00571188 http://link.springer.com/article/10.1007%2FBF00571188) Thus Jiang may have found a polynomial-time algorithm, but it solves a problem that is not NP-complete.
numbfits 13y ago
This video may help to understand the paper more vividly: http://www.youtube.com/watch?v=NYWgrjWQx60&feature=youtu.be http://www.youtube.com/watch?v=NYWgrjWQx60&feature=youtu...

44 points by Filligree 13y ago

Just 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 wide-reaching consequences. ... and prove its NP-completeness. 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. 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. Yes, yes it would. Now I'm off to see if I, as a non-specialist, can make any sense of it.

im3w1l 13y ago
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."
pedrocr 13y ago
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... :)
- ColinWright 13y ago
  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.
jb17 13y ago
> 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.

jacobparker 13y ago

ArXiv 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.

quarterto 13y ago
"Please don't submit comments complaining that a submission is inappropriate for the site." http://ycombinator.com/newsguidelines.html http://ycombinator.com/newsguidelines.html People have upvoted this article, therefore there should have been a submission for it.
- jacobparker 13y ago
  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 http://arxiv.org/abs/0809.4144
mixedbit 13y ago
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.
- dagw 13y ago
  Mathematically you can prove that an algorithm with certain properties exists, without being able to implement it. Also, as others have pointed out, polynomial does not necessarily mean "fast".
  - mixedbit 13y ago
    Interesting, are you aware of any such algorithm (proven to exist but not discovered yet)?

mixedbit 13y ago

From 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/ https://sites.google.com/site/xinwenjiang/

Filligree 13y ago
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.
mcintyre1994 13y ago
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.
samolang 13y ago
"Beware of bugs in the above code; I have only proved it correct, not tried it." - Donald Knuth
- devrelm 13y ago
  This appears to be a corollary: "Beware of bugs in the above code; I have only tried it, not proved it correct."

mebassett 13y ago

the 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.) related: http://primes.utm.edu/notes/crackpot.html http://primes.utm.edu/notes/crackpot.html

scythe 13y ago

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.

stiff 13y ago
Spot the error or shut up. If Ramajuan would write a paper himself he could only cite some rather obscure mathematical encyclopedia, he still uncovered wide areas of mathematics unknown to his contemporaries. There might be one Ramajuan for 100 000 cranks, but it still sucks to dismiss someones work based on the fucking bibliography...
- ColinWright 13y ago
  > Spot the error or shut up. That's not really how it works. I'm deciding whether it's worth my time trying to understand this. If it's really the breakthrough it purports to be, I can expect there to be some deep ideas and difficult tricks - I expect this to take both time and effort. To decide whether I'll bother I apply several heuristics, many of which are well-known and informally documented. If the first page or two just seems like obvious stuff, or is subtly nonsensical, then I won't bother. But I am certainly concerned that he doesn't cite any other significant work at all. More, the claims toward the end are rather, well, indistinct. It's doing very well against the ten heuristics in this blog post: http://www.scottaaronson.com/blog/?p=304 http://www.scottaaronson.com/blog/?p=304
  - raverbashing 13y ago
    Well, the best heuristic is finding a mistake, and if it's a crank there should be several.
    - ColinWright 13y ago
      It doesn't always work like that. Sometimes a paper is, after enough trying to understand what's going on, simply nonsense. It can be hard work wading through pages of unmotivated and apparently random definitions, trying to find some sense, only to have it completely fall apart. There aren't always obvious mistakes. Sometimes it makes sense locally, but not globally. Taking an early assessment can help enormously in avoiding time-wasters.

crntaylor 13y ago

I'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 http://www.scottaaronson.com/blog/?p=304)

glomph 13y ago
>At some point, there might be nothing left to do except to roll up your sleeves, brew some coffee, and tell your graduate student to read the paper and report back to you. Hahaha.

raverbashing 13y ago

Yes, 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)

stiff 13y ago

I spent some forty minutes on this, I think his "multistage graph simple path problem" is a very obfuscated version of a simpler problem where there is no need for this complicated labelling of vertices, with the information being instead reflected in the connections between vertices. I think the problem he discusses is simply the problem of determining whether two vertices in a graph are connected via a path or not. Did anyone else understand his problem formulation and had any similar impressions? I have a microscopic hope of this being a valid P=NP proof, still would be nice to know wtf is this about.

ColinWright 13y ago
His "Multistage Graph" seems poorly defined. I'm slowly coming to grasp what I think it is, but he defines is as G = <V,E,S,D,L> but pulls the E(v) from nowhere. It's not looking good.
- stiff 13y ago
  Yes, I think the intention is for E(v) to be one of the inputs of the algorithm (I contemplated E(v) for half an hour to guess this is what he means). I thought maybe the following is possible: I create a new graph with the same vertices as his graph, but instead of having an E(v) I connect each vertex to the members of E(v) via an edge. Afterwards, if two vertices are not connected via an edge in his original graph, I remove this edge from my new graph. I cannot really get to the heart of it, I just had a vague impression this might be equivalent, either way I think the problem could likely be formalized in a more effective way.
usamec 13y ago
Nope, there are constrains on how the path might look or not. The constrains have form: Is path enters vertex v, then it might only use edges {...}.
- ColinWright 13y ago
  Yes - it's getting harder and harder to pin down exactly what this problem really is, what an example of it is really like, and what's really going on. I'm sure the author has something in mind. I'm sure it's not well explained, and it might even prove insufficiently explained to be able to assess it properly. It's looking like it's locally "OK" but globally nonsense.

dburgoyne 13y ago

Jiang found a polynomial-time algorithm for solving what he calls "labelled multistage graphs" Note that these graphs are partially ordered sets (http://en.wikipedia.org/wiki/Partially_ordered_set http://en.wikipedia.org/wiki/Partially_ordered_set) and every partially ordered set has a unique corresponding comparability graph (http://en.wikipedia.org/wiki/Comparability_graph http://en.wikipedia.org/wiki/Comparability_graph) and the problem of finding a Hamiltonian cycle in a comparability graph is known not to be NP-complete. (http://link.springer.com/article/10.1007%2FBF00571188 http://link.springer.com/article/10.1007%2FBF00571188) Thus Jiang may have found a polynomial-time algorithm, but it solves a problem that is not NP-complete.

numbfits 13y ago

This video may help to understand the paper more vividly: http://www.youtube.com/watch?v=NYWgrjWQx60&feature=youtu.be http://www.youtube.com/watch?v=NYWgrjWQx60&feature=youtu...