I was extremely pleased to receive this informative email from professor 
Vaughan Pratt on October 6th, 2004, which gives insight into the history 
of the complexity of PRIMES.  The content of the email is published here 
with permission from Mr. Pratt.

Hi, Anton,

Just ran across across your very nice FAQ on primes, which was fun to 
read.

I couldn't help notice that while you talked about NP you didn't connect 
it up to the history of the complexity of primes.  I find the question of 
where the primes sit in respectively NP and P, in particular the relevant 
exponents in each case, to be very interesting, even today in the light of 
Agrawal et al.

That the primes are in NP (and hence in delta-P, the intersection of NP 
and
co-NP) was known informally since the 1960's (i.e. well before the concept 
of NP itself) to the very small set of people (which Rich Schroeppel and 
Bob Floyd told me they belong to) who'd noticed that the Lucas-Lehmer test 
was not just a heuristic like many other tests for primality (which was 
how the LL test was invariably described back then) but actually was 
applicable in some sense to *every* prime.

In the absence of the concept of NP, the obstacle to finding a suitable 
sense of this fact was the difficulty of finding a suitable primitive root 
and factorizing n-1.  The NP concept creates a meaningful setting in which 
it makes sense to simply guess a good primitive root and the factors of 
n-1 and then verify the guess afterwards.  I'd been aware of this test 
since the 60's, but it was not until Karp's NP concept had appeared that I 
noticed that the test put the primes in NP by being applicable to every 
prime.
I didn't think to write this up however, or even bother to mention it to 
anyone, since it seemed so obvious, until I mentioned it in some other 
context to Albert Meyer.  When he said that this couldn't be true or he'd 
have heard about it, I wrote it up to show him, and the writeup ended up a 
couple of years later in print (SiComp 4:3, 214-220, 1975).  The point of 
the "every" in "every prime has a succinct certificate" was to emphasize 
that the Lucas-Lehmer test was more than just a heuristic that worked only 
for some primes.  Some minor additional analysis turned out to be 
necessary to make the argument stick.

At about the same time Dick Karp pointed out that LP was in delta-P using 
a similarly straightforward extension of known results.  A little while 
later Kachijan pointed out that an exterior-point method known in the 
Russian literature but that had not yet made its way to the west for want 
of a translation demonstrated that LP was in P.  The corresponding passage 
for the primes had to wait quarter of a century for the recent Indian 
result.

However unlike LP, where the exponents are on the order of n^3.5 
(Karmarkar,
n^6 for Kachijan) for LP in P, the exponents for Primes in P are still up 
in the vicinity of n^12, with no progress downwards to date (that I'm 
aware of).
In that respect Primes seems harder than LP deterministically.

But nondeterministically there is no such gap between Primes and LP: both 
are comparably easy, somewhere in the vicinity of n^3 depending on exactly 
what n is taken to be, the machine model, etc.

Given that October 2002 was the date of the last edit to your FAQ, all 
this probably comes too late to be of use to it, but I thought at least 
you might find this perspective of interest yourself.

Vaughan Pratt