After reading 1 of the posts in this forum , I had a look at the millenium problems .(adsbygoogle = window.adsbygoogle || []).push({});

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

**Physics Forums - The Fusion of Science and Community**

# No of primes less than a given number

Have something to add?

- Similar discussions for: No of primes less than a given number

Loading...

**Physics Forums - The Fusion of Science and Community**