3

I'm learning about P and NP.
I've read that the problem of deciding if a given number is prime is a problem in P, which means that it has a polynomial-time algorithm which solves it.
I've also read that this fact was proven in 2002, with the algorithm of AKS.

As we all know, we can decide if a particular number is prime by running till its square root.

pseudo-code:

isPrime(N):

sqrt(N) <- squareRoot(N)

for i from 2 to Sqrt(N)
    if (n mod i == 0)
        return false
return true

My question is simple:
Why the algorithm above doesn't prove that this problem is in P?
Thanks :)

Mark Dickinson
  • 29,088
  • 9
  • 83
  • 120
Programmer
  • 750
  • 2
  • 9
  • 17
  • 3
    This question appears to be off-topic because it is belongs on the [Computer Science Stack Exchange](http://cs.stackexchange.com/). – nograpes Aug 16 '14 at 16:24

1 Answers1

8

Whether an algorithm is polynomial-time depends on the representation of the input. For example, the large number 9223372036854775807 fits in a 64-bit unsigned type. The significance of the AKS result is that it's polynomial in the number of bits (e.g., 64) rather than the number itself (e.g., 9223372036854775807).

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
  • 1
    Oh, I got it. So, if we let n be the number of bits represinting the number N, then the algorithm above is O(sqrt(2^n)), which is O(2 ^ (n/2))? – Programmer Aug 16 '14 at 16:31
  • OK, I got my answer. Thanks :) – Programmer Aug 16 '14 at 18:01
  • Very nice answer; to put it a different way, there is no complexity of "some mathematical problem" - the complexity depends on the specific representation of the encoding scheme of the input. Note that for checking for primality of `n`, using the naïve approach of division by all integers in the interval `[3..n-1]` yields a polynomial time algorithm - as long as _unary_ representation of the input is used. In fact, I needed a while to become aware of this, as presentation of complexity theory (as I experienced it) usually emphasizes the _problems_ themeselves more than the encoding schemes. – Codor Aug 18 '14 at 20:18