4 ms·

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 cour

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.

dagw 13y ago
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".
- mixedbit 13y ago
  Interesting, are you aware of any such algorithm (proven to exist but not discovered yet)?
  - philix001 13y ago
    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 http://en.wikipedia.org/wiki/Upper_and_lower_bounds
  - anonymoushn 13y ago
    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".
usamec 13y ago
O(n^10) algorithm is in P, but does not solve large inputs in reasonable time.
marcosdumay 13y ago
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.
- philix001 13y ago
  For a sufficiently big input (N) polynomial will be faster without any doubt.
raverbashing 13y ago
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.
- usamec 13y ago
  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.
  - raverbashing 13y ago
    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.
    - im3w1l 13y ago
      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.
kamaal 13y ago
>>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?

dagw 13y ago

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

mixedbit 13y ago
Interesting, are you aware of any such algorithm (proven to exist but not discovered yet)?
- philix001 13y ago
  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 http://en.wikipedia.org/wiki/Upper_and_lower_bounds
- anonymoushn 13y ago
  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".

usamec 13y ago

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

marcosdumay 13y ago

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.

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

raverbashing 13y ago

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.

usamec 13y ago
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.
- raverbashing 13y ago
  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.
  - im3w1l 13y ago
    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.

kamaal 13y ago

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