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

31–40 of 48 posts

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

#31

Post by raverbashing »

mixedbit wrote: post #17
jacobparker wrote: post #4

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.

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.

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.

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

#32

Post by ColinWright »

stiff wrote: post #30
ColinWright wrote: post #25

Earlier quoted context omitted.

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

The heuristics I apply go well beyond the ones given in that post. In this case I have taken on board the fact that so many references are just to his own earlier work, and that work is old enough that it should have made a bigger splash. That's a clear indication that this is not likely to be correct, so I'm looking for mistakes, I'm not looking for deep ideas.

And I'm not finding deep ideas. I spent 10 minutes getting a feel for the approach, and I'll come back when I have another 10 or 15 minutes to spare, but it's really, really not looking good.

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

#33

Post by ColinWright »

raverbashing wrote: post #29
ColinWright wrote: post #25

Earlier quoted context omitted.

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

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.

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

#34

Post by ColinWright »

usamec wrote: post #27
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 {...}.

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.

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

#35

Post by usamec »

raverbashing wrote: post #31
mixedbit wrote: post #17

Earlier quoted context omitted.

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.

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.

P=NP doesn't imply that there is fast algorithm for every problem in NP. It only means, that there is polynomial time algorithm for everything in NP (e.g. n^100 is polynomial). For example there can be O(n^100) algorithm for solving 3-SAT, which is not fast algorithm.

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

#36

Post by usamec »

ColinWright wrote: post #34
usamec wrote: post #27

Earlier quoted context omitted.

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

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.

Well, he get proving that his problem is NP-hard right (because the proof is really easy). But his algorithm for solving his problem is really messy and hard to follow.

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

#37

Post by dagw »

mixedbit wrote: post #17
jacobparker wrote: post #4

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.

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.

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

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

#38

Post by raverbashing »

usamec wrote: post #35
raverbashing wrote: post #31

Earlier quoted context omitted.

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.

P=NP doesn't imply that there is fast algorithm for every problem in NP. It only means, that there is polynomial time algorithm for everything in NP (e.g. n^100 is polynomial). For example there can be O(n^100) algorithm for solving 3-SAT, which is not fast algorithm.

Yes, but as usually, the problem with O is the growth

In the same way that Insertion sort can be faster than Quicksort for small vectors, there's a number of elements from where even O(n^100) is quicker than O(n!)

Because the (practical) problem with NP problems is not when they are small, you can try every combination for a small TSP problem in a reasonable time.

But for big problems, even if it's n^100 instead of n! it'll be most likely faster than the existing algos.

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

#39

Post by mixedbit »

dagw wrote: post #37
mixedbit wrote: post #17

Earlier quoted context omitted.

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.

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

Interesting, are you aware of any such algorithm (proven to exist but not discovered yet)?

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

#40

Post by philix001 »

mixedbit wrote: post #39
dagw wrote: post #37

Earlier quoted context omitted.

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

Interesting, are you aware of any such algorithm (proven to exist but not discovered yet)?

There are cases where the lower bound to solve some problems (e.g. sorting) have been proved to be less than any known algorithm at the time.

If you prove that the lower bound for any NP-Complete problem is O(p) where p is a polynomial, then P=NP and you do not necessarily have the algorithm.

http://en.wikipedia.org/wiki/Upper_and_lower_bounds

Post reply on HN