omags say u have a big number .
now say if u wanna no that if that number is PRIME.
can u figure it out FAST???
one slow way is 2 try 2 divide it by all number!!! (well, u only try the number that are smaler than its square root, u no!!!! or else infinity)
but this is SLOW!!
in fact, it takes EXPONENTIAL TIME !! (bacause number is represented in BINARY, ie, 0110101010201000200, when u write it , its length is logarithm in the number it self. so if u do operation that test all number less than it, it mean that self operation is EXPONENT, ie, 2^N in the size of inputs (1 and 0s!!) oopas!)
QUESTION is: can u do it in a poly-nomial time? so if number is K bits, can u solve IS-IT-PRIME-NUMBER with some numbar of steps like a*K^2000 + a*K^10 + a*K^4 + K or what ever??!
ANSER: coming 2 be anounced soon, is YES U CAN!!! (so the romer goes)
it is big solve, but it;s no P=NP i tell u! |
