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]
5 comments:
Integer factorization is not an NP-complete problem, it has nothing to do with P=NP whatsoever.
Integer factorization is not NP-complete, but it is in NP. Ergo, if P=NP then integer factorization is in P.
That's it. If one NP-complete is in P, than any other NP (complete or not) is also in P. Actually, an NP-complete problem is an NP problem to which any other NP can be reduced polynomially.
There are many errors in what you blogged and in the comments. You write "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." This is wrong. Firstly, the NP class is a class of problems not of algorithms. The same problem may have numerous algorithms with different running times. Secondly, it is not known that the NP-problems can not be solved in polynomial time as the sentence implies. This is what the whole P ?= NP is about! A more correct version of the sentence (yet not fully precise) is: "The NP class is the class of problems for which an algorithm exists that in polynomial time can verify if a given solution is correct".
And about integer factorization: It is unknown if integer factorization is NP-complete. It hasn't been proven either way. Integer factorization is in NP so if an NP-complete problem turns out to have a polynomial-time solution that would also lead to a polynomial solution to integer factorization. It is unknown if the converse is true.
This paper has been withdrawn Abstract: This paper has been withdrawn by the author due to the publication.
Post a Comment