Register to reply

No of primes less than a given number

by srijithju
Tags: number, primes
Share this thread:
srijithju
#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
Heat distributions help researchers to understand curved space
Professor quantifies how 'one thing leads to another'
Team announces construction of a formal computer-verified proof of the Kepler conjecture
Dragonfall
#2
Aug25-09, 05:30 PM
Dragonfall's Avatar
P: 993
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
#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
#4
Aug26-09, 02:15 PM
Dragonfall's Avatar
P: 993
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
#5
Aug26-09, 09:33 PM
Sci Advisor
HW Helper
P: 3,684
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
#6
Aug26-09, 10:14 PM
Dragonfall's Avatar
P: 993
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 Fun, Photos & Games 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