I was reading the arXiv 'headlines' today and found this. I am very skeptical about such breakthroughs once that the P=NP question is so important that it is one of the Millenium Prize problems.
For those who are not experts, I'll give a brief account of the problem. There are two main complexity classes of algorithms with respect to the time of computation: P and NP. The P class is the class of algorithms that give an answer in what is called polynomial time. This means that the time the algorithm takes to give you an answer is proportional to some power of the size of the question. This doesn't look so atractive if this power is very large, for example 20, but is always better than the NP class. The NP class is the class of algorithms which, although you can check if the solution is correct in polynomial time, if fed with a question they will take an exponential time with respect to the size of the question to give you an answer. If you remember your math classes, the exponential always grows faster than any polynomial. So, when the question gets big, it is really a problem.
The classical example, and the most important from the strategic/economic/etc point of view, is prime decomposition. Everybody knows that the public key cryptographic scheme is based on factoring an integer in two very large prime factors. This problem is NP, for the best algorithm known to solve the problem takes a time which is exponential in the size (the number of digits) of the number to be factorized. Note that I am not saying that there is no P algorithm which does that, only that it is not known. This is precisely the point: there is no proof that you cannot find a P algorithm to solve all problems. If you can, the cryptographic security of Internet is lost as codes could be broken very fast. There are fundamental issues that are also important, but I would say that security is one of the main concerns here...
Now, this guy claims that he found a P algorithm for every problem, whcih must include prime factorization. I will just point to the paper and wait for the revision of experts:
Does P=NP?
Karlen Garnik Gharibyan
arXiv:0705.1442v1 [cs.CC]
For those who are not experts, I'll give a brief account of the problem. There are two main complexity classes of algorithms with respect to the time of computation: P and NP. The P class is the class of algorithms that give an answer in what is called polynomial time. This means that the time the algorithm takes to give you an answer is proportional to some power of the size of the question. This doesn't look so atractive if this power is very large, for example 20, but is always better than the NP class. The NP class is the class of algorithms which, although you can check if the solution is correct in polynomial time, if fed with a question they will take an exponential time with respect to the size of the question to give you an answer. If you remember your math classes, the exponential always grows faster than any polynomial. So, when the question gets big, it is really a problem.
The classical example, and the most important from the strategic/economic/etc point of view, is prime decomposition. Everybody knows that the public key cryptographic scheme is based on factoring an integer in two very large prime factors. This problem is NP, for the best algorithm known to solve the problem takes a time which is exponential in the size (the number of digits) of the number to be factorized. Note that I am not saying that there is no P algorithm which does that, only that it is not known. This is precisely the point: there is no proof that you cannot find a P algorithm to solve all problems. If you can, the cryptographic security of Internet is lost as codes could be broken very fast. There are fundamental issues that are also important, but I would say that security is one of the main concerns here...
Now, this guy claims that he found a P algorithm for every problem, whcih must include prime factorization. I will just point to the paper and wait for the revision of experts:
Does P=NP?
Karlen Garnik Gharibyan
arXiv:0705.1442v1 [cs.CC]
