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

Re:P might be NP: A Polynomial Time Algorithm for the Hamilt... by mixedbit on Wednesday May 29, 2013 @12:56PM (#5787473)

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

[ Parent | on HN ]

Re:P might be NP: A Polynomial Time Algorithm for the Hamilt... by philix001 on Wednesday May 29, 2013 @01:33PM (#5787725)

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

[ Parent | on HN ]

Re:P might be NP: A Polynomial Time Algorithm for the Hamilt... by anonymoushn on Wednesday May 29, 2013 @08:17PM (#5790169)

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

[ Parent | on HN ]