- #1
srijithju
- 57
- 0
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
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