![](https://csdnimg.cn/release/download_crawler_static/10906103/bg4.jpg)
4 · David Johnson
where the J. Algorithms webpage makes scanned .pdf copies of all the columns
available for a fee.
2. CLOSED AND ALMOST CLOSED PROBLEMS
In this section, I discuss the four open problems that have been resolved/partially
resolved since the last column appeared. Two turned out to be polynomial-time
solvable, and I’ll start with these. As we shall see, although the results represent
major theoretical breakthroughs, the running times for the discovered algorithms
represent yet another strong challenge to the notion that “polynomial-time solv-
able” is a synonym for “efficiently solvable in practice.”
COMPOSITE NUMBER [G&J]
instance: Positive integer N.
question: Are there positive integers p, q > 1 such that N = p · q?
Comment: The search for an efficient algorithm for this problem goes back at
least to 1801, when Gauss discussed it in his Disquisitiones Arithmeticae. When the
NP-Completeness Column went on hiatus in 1992, it was known that the problem
was unlikely to be NP-complete. The complementary problem PRIMES (is N a
prime?) was known also to be in NP [Pratt 1975], and no problem in NP ∩ co-NP
can be NP-complete unless the polynomial hierarchy PH collapses to NP. Also,
there was an algorithm of Adleman et al. [1983] that tests for primality in time
n
O(log log n)
, where n = dlog Ne is the length of the binary representation of N (the
input size). Such a running time would apply to all other NP-complete problems
if primality testing were NP-complete. (Given that COMPOSITE NUMBER is in
P if and only if PRIMES is in P, I shall for simplicity refer to the problem under
consideration as “primality testing” in what follows.)
Still more was known about primality testing in 1992. In particular, it had re-
cently been shown to be in ZPP, the set of all problems solvable in polynomial
time by Las Vegas algorithms: randomized algorithms that for each instance either
report the correct answer or say “I don’t know,” the latter occurring with proba-
bility less than 1/2. This followed from a result of Adleman and Huang [1992], who
adapted the elliptic curve approach of Goldwasser and Kilian [1986] to show that
primes could be recognized by a polynomial-time Monte Carlo algorithm: a ran-
domized algorithm that says “no” if the input is composite and says “yes” at least
half the time when the input is prime. The Las Vegas algorithm was obtained by
running this algorithm in parallel with one of the previously-discovered polynomial-
time Monte Carlo algorithms for recognizing composite numbers [Rabin 1976; 1980;
Solovay and Strassen 1978]. Unfortunately, although the Monte Carlo algorithms
for composite numbers run in time O(n
2
log n log log n), the running time for the
Adleman-Huang algorithm is O(n
30
) or worse (M.-D. Huang, personal communi-
cation, 2005). This means that the Las Vegas algorithm was far from practical,
although its mere existence led many to conjecture that primality testing is in P.
Ten years later, in a preprint that was released on the Internet on August 6, 2002,
and covered in The New York Times just two days later, Manindra Agrawal, Neeraj
Kayal, and Nitin Saxena (AKS) verified this conjecture. The preprint [Agrawal
et al. 2002] showed that primality testing is indeed in P, essentially by proving
ACM Transactions on Algorithms, Vol. V, No. N, Month 20YY.