News for hackers. Stuff that matters.
Re:P might be NP: A Polynomial Time Algorithm for the Hamilt... by jacobparker on Wednesday May 29, 2013 @08:10AM (#5785787)
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.
Re:P might be NP: A Polynomial Time Algorithm for the Hamilt... by quarterto on Wednesday May 29, 2013 @08:18AM (#5785817)
"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.

Re:P might be NP: A Polynomial Time Algorithm for the Hamilt... by jacobparker on Wednesday May 29, 2013 @08:29AM (#5785860)
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

Re:P might be NP: A Polynomial Time Algorithm for the Hamilt... by mixedbit on Wednesday May 29, 2013 @08:36AM (#5785890)
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.

Re:P might be NP: A Polynomial Time Algorithm for the Hamilt... by usamec on Wednesday May 29, 2013 @08:40AM (#5785905)
O(n^10) algorithm is in P, but does not solve large inputs in reasonable time.
Re:P might be NP: A Polynomial Time Algorithm for the Hamilt... by dagw on Wednesday May 29, 2013 @11:05AM (#5786657)
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 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)?
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

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".
Re:P might be NP: A Polynomial Time Algorithm for the Hamilt... by raverbashing on Wednesday May 29, 2013 @09:47AM (#5786214)
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 Hamilt... by usamec on Wednesday May 29, 2013 @10:57AM (#5786600)
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 Hamilt... by raverbashing on Wednesday May 29, 2013 @11:09AM (#5786678)
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 Hamilt... by im3w1l on Wednesday May 29, 2013 @07:19PM (#5789898)
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 Hamilt... by kamaal on Thursday May 30, 2013 @02:14AM (#5791188)
>>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 Hamilt... by marcosdumay on Wednesday May 29, 2013 @08:49AM (#5785935)
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.
Re:P might be NP: A Polynomial Time Algorithm for the Hamilt... by philix001 on Wednesday May 29, 2013 @01:39PM (#5787765)
For a sufficiently big input (N) polynomial will be faster without any doubt.