P = NP

Finding a polynomial time algorithm for any NP complete problem suffices to prove that P equals NP. Finding the shortest route to visit a number of cities once and return to the starting city is an optimization problem known as the traveling salesman problem (TSP). NP encompasses optimization problems and the TSP is one of the NP complete problems. I found a polynomial time algorithm for the special case of the TSP where distances are either a or b (a and b are positive integers and a < b). The TSP remains NP complete in this special case. The algorithm finds an optimal tour and its worst case running time is quadratic in the number of vertices. And there is a proof of the correctness and upper limit of the algorithm. The algorithm, in essence, lies at the core of the TSP, and thus, it throws light on the complexity of the TSP.

Prime factorization is an NP problem. RSA, a public key protocol widely used to secure data transmission over the Internet, works by using arithmetic modulo the product of two large prime numbers and relies on the assumption that factoring a number that is the product of two prime numbers with hundreds of digits is hard. An efficient algorithm for prime factorization can break RSA. Using the algorithm I found, I’ll soon factor all RSA numbers in the RSA Factoring Challenge that haven’t been factored so far, including RSA2048, and I’ll publish the solutions on this blog. I’ll start with RSA260.