P=NP implies a deterministic algorithm to find primes: Difference between revisions
New page: Consider the decision problem of determining whether there is a prime in the range <math>[m,n]</math>, where <math>m < n</math>. This problem is in NP, since if there is a prime in the ra... |
No edit summary |
||
| Line 1: | Line 1: | ||
Consider the decision problem of determining whether there is a prime in the range <math>[m,n]</math>, where <math>m < n</math>. This problem is in NP, since if there is a prime in the range, we can efficiently verify that it is prime. By assumption, this decision problem is therefore in P, | Consider the decision problem of determining whether there is a prime in the range <math>[m,n]</math>, where <math>m < n</math>. This problem is in NP, since if there is a prime in the range, we can efficiently verify that it is prime. By assumption, this decision problem is therefore in P, i.e., there is a polynomial-time algorithm to determine whether there is a prime in the range <math>[m,n]</math>. | ||
We can use this algorithm as a subroutine to quickly find a prime in the range [n,2n] for large n. We use the well-known fact that such a prime always exists. We then use the polynomial-time algorithm described above to do a binary search to locate such a prime. This terminates after at most <math>\log_2 n</math> applications of the subroutine, and thus is a polynomial-time algorithm to generate a prime. | We can use this algorithm as a subroutine to quickly find a prime in the range [n,2n] for large n. We use the well-known fact that such a prime always exists. We then use the polynomial-time algorithm described above to do a binary search to locate such a prime. This terminates after at most <math>\log_2 n</math> applications of the subroutine, and thus is a polynomial-time algorithm to generate a prime. | ||
Revision as of 14:26, 28 July 2009
Consider the decision problem of determining whether there is a prime in the range [math]\displaystyle{ [m,n] }[/math], where [math]\displaystyle{ m \lt n }[/math]. This problem is in NP, since if there is a prime in the range, we can efficiently verify that it is prime. By assumption, this decision problem is therefore in P, i.e., there is a polynomial-time algorithm to determine whether there is a prime in the range [math]\displaystyle{ [m,n] }[/math].
We can use this algorithm as a subroutine to quickly find a prime in the range [n,2n] for large n. We use the well-known fact that such a prime always exists. We then use the polynomial-time algorithm described above to do a binary search to locate such a prime. This terminates after at most [math]\displaystyle{ \log_2 n }[/math] applications of the subroutine, and thus is a polynomial-time algorithm to generate a prime.
