01 March 2013

P or not-P

  • Algorithms that run quickly are said to be class P. The letter stands for ‘polynomial’—yes, it’s starting to sound like math now—which describes how rapidly the computational time grows as the size of the input increases. 
All other algorithms are not-P, and run too slowly to be useful,

  • We can prove beyond a shadow of doubt that some problems are not-P. “Write every possible book” is an example: whichever algorithm you use, it has to output the answer, and that takes forever. 
The class NP rules out silly problems like this one. It pins down the potentially hard problems that have short and snappy answers. 

  • The letters stand for “nondeterministic polynomial” ~ and the n-word means that you guess.
Got you all titivated and sexed up? Knew I would.

No comments :