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
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...ch+Books:+%27devlin+the+millenium+problems%27
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 .
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.
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.