Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

arxiv.org

Post reply on HN
Print view View original

21–30 of 48 posts

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

#21

Post by stiff »

scythe wrote: post #11

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.

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

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

#22

Post by devrelm »

samolang wrote: post #16
mixedbit wrote: post #8

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/

"Beware of bugs in the above code; I have only proved it correct, not tried it." - Donald Knuth

This appears to be a corollary: "Beware of bugs in the above code; I have only tried it, not proved it correct."

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

#23

Post by glomph »

crntaylor wrote: post #12

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.sco…

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

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

#24

Post by stiff »

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.

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

#25

Post by ColinWright »

stiff wrote: post #21
scythe wrote: post #11

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.

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

    > 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

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

#26

Post by ColinWright »

stiff wrote: post #24

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

His "Multistage Graph" seems poorly defined. I'm slowly coming to grasp what I think it is, but he defines is as

    G =
but pulls the E(v) from nowhere.

It's not looking good.

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

#27

Post by usamec »

stiff wrote: post #24

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

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 {...}.

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

#28

Post by stiff »

ColinWright wrote: post #26
stiff wrote: post #24

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

His "Multistage Graph" seems poorly defined. I'm slowly coming to grasp what I think it is, but he defines is as G = but pulls the E(v) from nowhere. It's not looking good.

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.

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

#29

Post by raverbashing »

ColinWright wrote: post #25
stiff wrote: post #21

Earlier quoted context omitted.

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

> 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 o…

Well, the best heuristic is finding a mistake, and if it's a crank there should be several.

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

#30

Post by stiff »

ColinWright wrote: post #25
stiff wrote: post #21

Earlier quoted context omitted.

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

> 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 o…

OK, but I would love for those heuristics to focus on assessing the content of the paper, not the reputation of the author, his peers and quotations etc. You can get some vague impression of what's going on in this paper in some 30 minutes, there are many parts that seem strange (he says for 4-stage graphs one can manually verify that his "prooving algorithm" is correct and uses this as an assumption later in his proof), so I would love to hear something about that.
Post reply on HN