No of primes less than a given number


by srijithju
Tags: number, primes
srijithju
srijithju is offline
#1
Aug25-09, 02:18 PM
P: 57
After reading 1 of the posts in this forum , I had a look at the millenium problems .
There I saw the problem of proving if N=NP .

I really did not understand what is NP and what is P ( I checked the Wikipedia link but this got me even more confused ... It talked of a non deterministic Turing machine whatever that is )

This is my doubt :
There exists an algorithm (AKS algorithm) which is able to calculate if a number is prime in with polynomial complexity.

Now if it is proved that N=NP , does that imply that you can also develop an algorithm to find all primes less than or equal to a prime in polynomial time ?

Could someone suggest some literature where I can read about what NP / P complexity classes are. Also I am not sure of what exactly is the meaning of polynomial complexity also with respect to treatment of integers ( for eg. checking if N is prime)


This is my understanding of complexity of an algo:
Complexity refers to number of calculations to be done by a computer to reach the result ( find the solution) expressed as a function of the size of the input.

Now to check if N is prime we would first have to express N as a binary number. Now in the process of checking if it is prime we may have to add / multiply / divide these numbers . What we be the complexities of these individual steps ..
To add 2 numbers we get answer in 1 step ( 1 clock cycle of ALU of computer) if the size of number is within the CPU register width , but if it exceeds this width we need more cycles depending on how large the number is . Similarly for multiplication and division . So how do we calculate the actual complexity of a specific problem ???
Please help
Phys.Org News Partner Mathematics news on Phys.org
Researchers help Boston Marathon organizers plan for 2014 race
'Math detective' analyzes odds for suspicious lottery wins
Pseudo-mathematics and financial charlatanism
Dragonfall
Dragonfall is offline
#2
Aug25-09, 05:30 PM
Dragonfall's Avatar
P: 992
You can think of NP as the class of problems whose solutions can be VERIFIED in polynomial time. ie, if I ask you to factor N, and you give me p and q, I can multiply them easily and check whether N=pq. While P is the class of problems whose solutions can be COMPUTED in polynomial-time, like sorting N numbers.

Even if P=NP, there might not be a polynomial-time algorithm that will compute the number of primes less than N exactly. But I think this is due to our lack of understanding of the prime numbers rather than complexity. So this would be a problem in number theory, not computational complexity.

Any textbook on "computational complexity" will do. But I suggest taking a course if you really want to learn about it.

If you just want a superficial understanding of the millennium problems (it would take a lot of math to truly understand any of them), read http://www.chapters.indigo.ca/books/...+problems%2527
srijithju
srijithju is offline
#3
Aug26-09, 01:24 PM
P: 57
Thanks a lot for the reply ...

Quote Quote by Dragonfall View Post
Even if P=NP, there might not be a polynomial-time algorithm that will compute the number of primes less than N exactly. But I think this is due to our lack of understanding of the prime numbers rather than complexity. So this would be a problem in number theory, not computational complexity.
yes I can see that maybe the reason we cannot calculate all primes < N in polynomial time is probably due to our lack of understanding of number theory, but what I mean to as is if P=NP , then does not that mean that theoretically an algo exists that can compute primes < N in polynomial time , though we are unaware of such an algo.


Now regarding the explanation you gave of a P problem and an NP problem -

So if we consider the problem of finding all the prime numbers then that means :

a) This problem is most certainly a NP problem because we already know of an algorithm that can verify a certain solution ( i.e. can check if a given number is prime) in polynomial time.
b) But we are not sure if the problem is P .

But considering this problem - is this not a counter example to showing P=NP , because we know there are infinitely many primes so how are we supposed to calculate an infinite number of solutions in polynomial time ? - or is it that all the prime numbers can be expressed by some formula ( which at present we do not know of) , and it is enough to find this formula in polynomial time .

Dragonfall
Dragonfall is offline
#4
Aug26-09, 02:15 PM
Dragonfall's Avatar
P: 992

No of primes less than a given number


Quote Quote by srijithju View Post
yes I can see that maybe the reason we cannot calculate all primes < N in polynomial time is probably due to our lack of understanding of number theory, but what I mean to as is if P=NP , then does not that mean that theoretically an algo exists that can compute primes < N in polynomial time , though we are unaware of such an algo.
Do you mean compute a prime < N, compute all primes < N, or the number of primes < N?

Quote Quote by srijithju View Post
So if we consider the problem of finding all the prime numbers then that means :

a) This problem is most certainly a NP problem because we already know of an algorithm that can verify a certain solution ( i.e. can check if a given number is prime) in polynomial time.
"Finding all the primes" less than N is certainly not an NP problem, because there's no way you can verify all the approx. N/log N many primes in polynomial time. This problem isn't even in PSPACE.

However, finding a prime less than N is NP. In fact, it's most likely P. However since this problem isn't NP-hard, the existence of a polynomial-time algorithm for solving it does not mean P=NP.

I don't know how hard finding the number of primes less than N is.
CRGreathouse
CRGreathouse is offline
#5
Aug26-09, 09:33 PM
Sci Advisor
HW Helper
P: 3,680
Quote Quote by Dragonfall View Post
I don't know how hard finding the number of primes less than N is.
The best known algorithm is exponential -- time ~ n^(1/2 + eps). I don't think there's any hope for finding a polynomial algorithm.
Dragonfall
Dragonfall is offline
#6
Aug26-09, 10:14 PM
Dragonfall's Avatar
P: 992
Quote Quote by CRGreathouse View Post
The best known algorithm is exponential -- time ~ n^(1/2 + eps). I don't think there's any hope for finding a polynomial algorithm.
Do you mean (1/2+eps)^n?

There might not be a polynomial algorithm to find the exact number, but it can be approximated very well -- the prime number theorem, for example -- by polynomial algorithms.

I don't know where this problem sits in the hierarchy, either.


Register to reply

Related Discussions
Sum the three primes, get number Brain Teasers 0
Question about primes and divisibility...abstract algebra/number theory General Math 6
number theory - primes Calculus & Beyond Homework 3
Number Theory - divisibility and primes Calculus & Beyond Homework 1
Is the number of twin primes really infinite? Linear & Abstract Algebra 6