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

by Filligree • 13 years ago

44 47 13 years ago

ColinWright7• 13 years 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.

im3w1l2• 13 years 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• 13 years 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... :)

ColinWright7• 13 years 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• 13 years 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.

jacobparker2• 13 years 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• 13 years ago

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

jacobparker2• 13 years 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

mixedbit3• 13 years 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.

usamec4• 13 years ago

O(n^10) algorithm is in P, but does not solve large inputs in reasonable time.

marcosdumay• 13 years ago

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.

raverbashing4• 13 years ago

Exactly.

I believe there's good money to be made if you find out that P=NP

If you can solve an NP problem in polynomial time you can solve 3-SAT, and if you can solve that you can factor big numbers (even though factorization is 'easier' than NP)

Maybe you can easily reverse hash functions as well with that knowledge.

dagw• 13 years 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".

kamaal• 13 years ago

>>This of course wouldn't prove the work is valid

No, it actually would. And exactly the question begs the answer why don't they submit the damn code.

During my college days, a professor would always argue combustion can only be a exothermic reaction. Another professor would argue it can endothermic too. By the way the discussions went and during one lab session, a student just stood up and asked the professor to produce a chemical which he could put on his palm and burn to prove its endothermic.

Since then he stopped and I never ever heard him talking about combustion being a endothermic reaction again.

All it takes is to write a program, if you have the algorithm is it really that difficult to write it?

mixedbit3• 13 years 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/

Filligree• 13 years 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• 13 years 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• 13 years ago

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

devrelm• 13 years ago

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

mebassett• 13 years 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.)

scythe• 13 years 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.

stiff4• 13 years 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...

ColinWright7• 13 years 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

emorning2• 13 years ago

Well, that's not just some textbook on computational complexity, it's the textbook on computational complexity.

numbfits2• 13 years ago

The field of "p versus np" is seldom being touched by researchers, since no one wanna spend his/her time on an unknown ending research program. What I mean maybe one could hardly find a published paper in recent years. What do you expect the author to cite? If you want to get an overview about the paper, you may watch this: http://www.youtube.com/watch?v=NYWgrjWQx60&feature=youtu...

crntaylor• 13 years 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)

glomph• 13 years 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.

raverbashing4• 13 years 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)

stiff4• 13 years 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.

ColinWright7• 13 years 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.

stiff4• 13 years 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.

usamec4• 13 years 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 {...}.

ColinWright7• 13 years 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• 13 years 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)

and every partially ordered set has a unique corresponding 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)

Thus Jiang may have found a polynomial-time algorithm, but it solves a problem that is not NP-complete.

numbfits2• 13 years ago

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

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

Related Stories