Register to reply 
No of primes less than a given number 
Share this thread: 
#1
Aug2509, 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 


#2
Aug2509, 05:30 PM

P: 995

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 polynomialtime, like sorting N numbers.
Even if P=NP, there might not be a polynomialtime 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 


#3
Aug2609, 01:24 PM

P: 57

Thanks a lot for the reply ...
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 . 


#4
Aug2609, 02:15 PM

P: 995

No of primes less than a given number
However, finding a prime less than N is NP. In fact, it's most likely P. However since this problem isn't NPhard, the existence of a polynomialtime algorithm for solving it does not mean P=NP. I don't know how hard finding the number of primes less than N is. 


#5
Aug2609, 09:33 PM

Sci Advisor
HW Helper
P: 3,684




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 