Hacker News Reader

Comment by jacobparker | Hacker News Reader

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.

View on HN

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

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

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.

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

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.

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.

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.

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

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

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

Reply on news.ycombinator.com