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

41–48 of 48 posts

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

#41

Post by philix001 »

marcosdumay wrote: post #19
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.

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.

For a sufficiently big input (N) polynomial will be faster without any doubt.

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

#42

Post by emorning2 »

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.

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

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

#43

Post by im3w1l »

raverbashing wrote: post #38
usamec wrote: post #35

Earlier quoted context omitted.

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…

The problem is that, even though it is faster it isn't fast enough. You can't solve any real world large problems with a n^100 algo, even though it is faster in theory.

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

#44

Post by anonymoushn »

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)?

A bit more weakly, some algorithms are known but do not have any implementations. I believe this is the case for the algorithm from "Triangulating a Simple Polygon in Linear Time".

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

#45

Post by kamaal »

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.

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

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

#46

Post by dburgoyne »

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.

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

#48

Post by numbfits »

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.

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...
Post reply on HN