No of primes less than a given number

  1. 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
  2. jcsd
  3. 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
    Last edited: Aug 25, 2009
  4. Thanks a lot for the reply ...

    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 .
  5. Do you mean compute a prime < N, compute all primes < N, or the number of primes < N?

    "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.
    Last edited: Aug 26, 2009
  6. CRGreathouse

    CRGreathouse 3,497
    Science Advisor
    Homework Helper

    The best known algorithm is exponential -- time ~ n^(1/2 + eps). I don't think there's any hope for finding a polynomial algorithm.
  7. 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.
Know someone interested in this topic? Share this thead via email, Google+, Twitter, or Facebook

Have something to add?
Similar discussions for: No of primes less than a given number