What Does it Mean that PRIMES is in P?

Abstract

In August 2002, three Indian computer scientists published a paper entitled `PRIMES is in P' online. It presents a `deterministic algorithm' which determines in `polynomial time' if a given number is a prime number. The story was quickly picked up by the general press, and by this means spread through the scientific community of complexity theorists, where it was hailed as a major theoretical breakthrough. This is despite scientists regarding the media reports as vulgar popularizations. When the paper was published in a peer-reviewed journal only 2 years later, the three scientists had already received wide recognition for their accomplishment. Current sociological theory challenges the ability to clearly distinguish on independent epistemic grounds between distorted and non-distorted scientific knowledge. It views the demarcation lines between such forms of presentation as contextual and unstable. In my paper, I challenge this view. By systematically surveying the popular press coverage of the `PRIMES is in P' affair, I argue — against the prevailing new orthodoxy — that distorted simplifications of scientific knowledge are distinguishable from non-distorted simplifications on independent epistemic grounds. I argue that in the `PRIMES is in P' affair, the three scientists could ride on the wave of the general press-distorted coverage of their algorithm, while counting on their colleagues' ability to distinguish genuine accounts from distorted ones. Thus, their scientific reputation was unharmed. This suggests that the possibility of the existence of independent epistemic standards must be incorporated into the new SSK model of popularization.