@article{Slot&van.Emde.Boas:1988,
	key = "Slot and van Emde Boas 1988",
 	author = "C. Slot and P. van Emde Boas",
 	title = "The Problem of Space Invariance for Sequential Machines",
 	journal = IC,
 	volume = 77,
 	pages = "93-122",
 	year = "1988"}

@article{Cook&Reckhow:1973,
	key = "Cook and Reckhow 1973",
 	author = "S. A. Cook and R. A. Reckhow",
 	title = "Time Bounded Random Access Machines",
 	journal = JCSS,
 	volume = 7,
 	pages = "354-375",
 	year = 1973}

@article{Katajainen&van.Leeuwen.Penttonen:1988,
 	key = "Katajainen, van Leeuwen, and Penttonen 1988",
 	author = "J. Katajainen and J. van Leeuwen and M. Penttonen",
 	title = "Fast Simulation of {Turing} Machines by 
                 Random Access Machines",
 	journal = SIAMJC,
 	volume = 17,
 	pages = "77-88",
 	year = 1988}

@incollection{Borodin:1973,
	key = "Borodin 1973",
	author = "A. Borodin",
  	title = "Computational complexity: theory and practice",
  	booktitle = "Currents in the Theory of Computing",
  	editor = "A. V. Aho",
  	publisher = PH,		
  	year = 1973,
  	pages = "35-89"} % Prentice-Hall
  
@article{Shannon:1948,
 	key = "Shannon 1948",
 	author = "C. E. Shannon",
 	title = "A mathematical theory of communication (part {I})",
 	journal = BSTJ,
 	volume = 27,
 	pages = "379-423",
 	year = 1948}

@article{Borwein:1985,
 	key = "Borwein 1985",
 	author = "P. B. Borwein",
 	title = "On the complexity of calculating factorials",
 	journal = JA,
 	volume = 6,
 	pages = "376-380",
 	year = 1985}

@article{SchoenhageStrassen:1971,
 	key = "Sch{\"o}nhage and Strassen 1971",
 	author = "A. Sch{\"o}nhage and V. Strassen",
 	title = "Schnelle {Multiplikation} Gro{\ss}er {Zahlen}",
 	journal = COMP,	
 	volume = 7,
 	pages = "281-292",
 	year = 1971}

@article{Karatsuba&Ofman:1962,
 	key = "Karatsuba and Ofman 1962",
 	author = "A. A. Karatsuba and Y. Ofman",
 	title = "Multiplication of multidigit numbers by automata",
 	journal = DAN,
 	volume = 145,
 	pages = "293-294",
 	year = 1962,
	note = "English translation in {\it Soviet Physics Doklady}
{\bf 7} (1963), 595--596"}

@incollection{Maeder:1993,
	key = "Maeder 1993",
	author = "R. E. Maeder",
	title = "Storage allocation for the {Karatsuba} integer
multiplication algorithm",
	booktitle = DISCO93,
	editor = "A. Miola",
	series = LNICS,
	publisher = SV,
	volume = 722,
	year = 1993,
	pages = "59-65"}

@article{Turing:1939,
 	key = "Turing 1939",
 	author = "A. M. Turing",
 	title = "Systems of logic based on ordinals",
 	journal = PLMS,
 	volume = 45,
 	pages = "161-228",
 	year = 1939}	% Proceedings of the London Mathematical Society (2)

@inproceedings{Cook:1971,
  	key = "Cook 1971",
  	author = "S. A. Cook",
  	title = "The Complexity of Theorem-Proving Procedures",
  	booktitle = STOC71,
  	publisher = "ACM Press",
  	year = 1971,
  	pages = "151-158"}
  
@inproceedings{Cook:1973,
  	key = "Cook 1973",
  	author = "S. A. Cook",
  	title = "An Observation on Time-Storage Tradeoff",
  	booktitle = STOC73,
  	publisher = "ACM Press",
  	year = 1973,
  	pages = "29-33"}
  
% more NP-complete number theoretic problems:

@article{Eppstein:1987,
 	key = "Eppstein 1987",
 	author = "D. Eppstein",
 	title = "On the {NP-completeness} of cryptarithms",
 	journal = SIGACT,	
 	volume = 18,
	number = 3,
 	pages = "38-40",
 	year = 1987}     % Sigact News

@techreport{Gurari&Ibarra:1977,
  	key = "Gurari and Ibarra 1977",
  	author = "E. M. Gurari and O. H. Ibarra",
  	title = "An {NP-complete} number-theoretic problem",
  	institution = "University of Minnesota, Computer Science Department",
  	number = "77-12",
  	month = "August",
  	year = 1977}

@article{Gurari&Ibarra:1979,
	key = "Gurari and Ibarra 1979",
	author = "E. M. Gurari and O. H. Ibarra",
	title = "An {NP-complete} number-theoretic problem",
	journal = JACM,
	volume = 26,
	year = 1979,
	pages = "567-581"}

@article{Manders&Adleman:1978,
	key = "Manders and Adleman 1978",
	title = "{NP-complete} decision problems for binary quadratics",
	author = "K. L. Manders and L. Adleman",
	journal = JCSS,
	volume = 16,
	year = 1978,
	pages = "168-184"}

% anti-CRT: Stockmeyer and Meyer 1973

@article{Levin:1973,
 	key = "Levin 1973",
 	author = "L. Levin",
 	title = "Universal sequential search problems",
 	journal = PPI,	
 	volume = 9,
 	number = 3,
 	pages = "115-116",
 	year = 1973,
	note = "English translation in {\it Problems of Information 
                   Transmission} {\bf 9} (1973), 265--266."
	}

@incollection{von.Neumann:1947,
	key = "von Neumann 1947",
	author = "Neumann, J. von",
  	title = "Letter to {R.} {D.} {Richtmyer}, {March} 11, 1947",
  	booktitle = "John von Neumann: Collected Works, vol. V",
  	editor = "A. H. Taub",
  	publisher = PERG,	
  	year = "{\noopsort{1947}}1963",
  	pages = "751-764"}

@inproceedings{Adleman:1978,
  	key = "Adleman 1978",
  	author = "L. M. Adleman",
  	title = "Two Theorems on Random Polynomial Time",
  	booktitle = FOCS78,
  	publisher = "IEEE Press",
  	year = 1978,
  	pages = "75-83"}
  
@article{Gill:1977,
 	key = "Gill 1977",
 	author = "J. Gill",
 	title = "Computational Complexity of Probabilistic {Turing} Machines",
 	journal = SIAMJC,
 	volume = 6,
 	pages = "675-695",
 	year = 1977}

@article{Minsky:1961,
 	key = "Minsky 1961",
 	author = "M. L. Minsky",
 	title = "Recursive unsolvability of {Post's} problem of ``tag''
                 and other topics in the theory of {Turing} machines",
 	journal = AM,
 	volume = 74,
 	pages = "437-455",
 	year = 1961}

@article{Yamada:1962,
 	key = "Yamada 1962",
 	author = "H. Yamada",
 	title = "Real-time computation and recursive functions
		 not real-time computable",
 	journal = IEEE-EC,	
 	volume = "EC-11",
 	pages = "753-760",
 	year = 1962} % IEEE Trans. Elect. Comput.

@article{Hartmanis&Stearns:1965,
 	key = "Hartmanis and Stearns 1965",
 	author = "J. Hartmanis and R. E. Stearns",
 	title = "On the computational complexity of algorithms",
 	journal = TAMS,
 	volume = 117,
 	pages = "285-306",
 	year = 1965}

@incollection{de.Leeuw&Moore&Shannon&Shapiro:1956,
	key = "de Leeuw, Moore, Shannon, and Shapiro 1956",
	author = "Leeuw, K. de and E. F. Moore and 
                  C. E. Shannon and N. Shapiro",
  	title = "Computability by probabilistic machines",
  	booktitle = "Automata Studies",
  	editor = "C. E. Shannon and J. McCarthy",
  	publisher = PUP,	
  	year = 1956,
  	pages = "183-212", 
	comment = "Princeton, Annals of Mathematics Studies #34" }


@article{Greibach:1981,
 	key = "Greibach 1981",
 	author = "S. A. Greibach",
 	title = "Formal languages: origins and directions",
 	journal = AHC,	
 	volume = 3,
 	pages = "14-41",
 	year = 1981}    

@book{Garey&Johnson:1979,
  	key = "Garey and Johnson 1979",
  	author = "M. R. Garey and D. S. Johnson",
  	title = "Computers and Intractability: A Guide to the Theory
		 of {NP-Completeness}",
  	publisher = FRMN,
  	year = 1979}

@incollection{Karp:1972,
	key = "Karp 1972",
	author = "R. M. Karp",
  	title = "Reducibility among combinatorial problems",
  	booktitle = "Complexity of Computer Computations",
  	editor = "R. E. Miller and J. W. Thatcher",
  	publisher = PLNM,	
  	year = 1972,
  	pages = "85-103"}

@article{Johnson:1984,
 	key = "D. Johnson 1984",
 	author = "D. S. Johnson",
 	title = "The {NP-completeness} column: an ongoing guide",
 	journal = JA,
 	volume = 5,
 	pages = "433-447",
 	year = 1984}

@unpublished{Finn:1982a,
 	key = "Finn 1982a",
 	author = "J. Finn",
 	title = "Comparison of Probabilistic Tests for Primality",
 	note = "Unpublished manuscript, undated, c.",
 	year = "{\noopsort{1982a}}1982", 
	comment = "Not sure of date.  Cf. Princeton TR 297, 
		   reference to ANC algorithms." }

@inproceedings{Stockmeyer&Meyer:1973,
  	key = "Stockmeyer and Meyer 1973",
  	author = "L. J. Stockmeyer and A. R. Meyer",
  	title = "Word problems requiring exponential time",
  	booktitle = STOC73,
  	publisher = "ACM Press",
  	year = 1973,
  	pages = "1-9"}

@book{Hopcroft&Ullman:1979,
  	key = "Hopcroft and Ullman 1979",
  	author = "J. E. Hopcroft and J. D. Ullman",
  	title = "Introduction to Automata Theory, Languages, and Computation",
  	publisher = AW,	
  	year = 1979}

@article{Garey&Johnson:1978,
 	key = "Garey and Johnson 1978",
 	author = "M. R. Garey and D. S. Johnson",
 	title = "{``Strong''} {NP-completeness} results: motivation, examples,
                and implications",
 	journal = JACM,	
 	volume = 25,
 	pages = "499-508",
 	year = 1978}

@article{Bach:1988,
 	key = "Bach 1988",
 	author = "E. Bach",
 	title = "How to generate factored random numbers",
 	journal = SIAMJC,
 	volume = 17,
 	pages = "179-193",
 	year = 1988}

@article{Beame&Cook&HooverCH:1986,
 	key = "Beame, Cook, and Hoover 1986",
 	author = "P. W. Beame and S. A. Cook and H. J. Hoover",
 	title = "Log depth circuits for division and related problems",
 	journal = SIAMJC,
 	volume = 15,
 	pages = "994-1003",
 	year = 1986}

@article{Ofman:1962,
 	key = "Ofman 1962",
 	author = "Y. Ofman",
 	title = "On the algorithmic complexity of discrete functions",
 	journal = DAN,	
 	volume = 145,
 	pages = "48-51",
 	year = 1962,
	note = "English translation in {\it Soviet Physics Doklady},
		{\bf 7} (1963), 589--591."
	}

@article{Vitanyi:1988,
 	key = "{Vit\'anyi} 1988",
 	author = "P. M. B. {Vit\'anyi}",
 	title = "Locality, communication, and interconnect length in
		 multicomputers",
 	journal = SIAMJC,
 	volume = 17,
 	pages = "659-672",
 	year = 1988}	

@article{Sutherland&Mead:1977,
 	key = "Sutherland and Mead 1977",
 	author = "I. E. Sutherland and C. A. Mead",
 	title = "Microelectronics and computer science",
 	journal = SA,
 	volume = 237,
	number = 3,
 	pages = "210-229",
 	year = 1977}	

@article{Wallace:1964,
 	key = "Wallace 1964",
 	author = "C. S. Wallace",
 	title = "A suggestion for a fast multiplier",
 	journal = IEEE-EC,
 	volume = "EC-13",
 	pages = "14-17",
 	year = 1964}	

@article{Anderson&Earle&Goldschmidt&Powers:1967,
	key = "Anderson, Earle, Goldschmidt, and Powers 1967",
 	author = "S. F. Anderson and J. G. Earle and R. E. Goldschmidt 
                  and D. M.  Powers",
 	title = "The {IBM} {System/360} {Model} 91: 
                 floating-point execution unit",
 	journal = IBMJ,	
 	volume = 11,
 	pages = "34-53",
 	year = 1967}

@techreport{Bach&Sorenson:1989,
  	key = "Bach and Sorenson 1989",
  	author = "E. Bach and J. Sorenson",
  	title = "Sieve algorithms for perfect power testing",
  	institution = "University of Wisconsin, Computer Sciences Department",
  	number = "852",
  	month = "June",
  	year = 1989}

@article{Bach&Sorenson:1993,
	key = "Bach and Sorenson 1993",
	author = "E. Bach and J. Sorenson",
	title = "Sieve algorithms for perfect power testing",
	journal = "Algorithmica",
	volume = 9,
	year = 1993,
	pages = "313-328"}

% Books: Waser and Flynn, etc.

@incollection{Knuth&Yao:1976,
	key = "Knuth and Yao 1976",
	author = "D. E. Knuth and A. C. Yao",
  	title = "The complexity of nonuniform random number generation",
  	booktitle = "Algorithms and Complexity: New Directions and Recent
		     Results",
  	editor = "J. F. Traub",
  	publisher = AP,
  	year = 1976,
  	pages = "357-428"}

@article{Jones&Laaser:1977,
 	key = "N. Jones and Laaser 1977",
 	author = "N. D. Jones and W. T. Laaser",
 	title = "Complete problems for deterministic polynomial time",
 	journal = TCS,
 	volume = 3,
 	pages = "105-117",
 	year = 1977}	

@article{Ladner:1975,
 	key = "Ladner 1975",
 	author = "R. E. Ladner",
 	title = "The circuit value problem is log space complete for {P}",
 	journal = SIGACT,
 	volume = 7,
	number = 1,
 	pages = "18-20",
 	year = 1975
	}	

@inproceedings{Pippenger:1979,
  	key = "Pippenger 1979",
  	author = "N. Pippenger",
  	title = "On simultaneous resource bounds",
  	booktitle = FOCS79,
  	publisher = "IEEE Press",
  	year = 1979,
  	pages = "307-311"}

@inproceedings{Mansour&Schieber&Tiwari:1989,
  	key = "Mansour, Schieber and Tiwari 1989",
  	author = "Y. Mansour and B. Schieber and P. Tiwari",
  	title = "The complexity of approximating the square root",
  	booktitle = FOCS89,
  	publisher = "IEEE Press",
  	year = 1989,
  	pages = "325-330"}

@article{Karloff&Ruzzo:1989,
 	key = "Karloff and Ruzzo 1989",
 	author = "H. J. Karloff and W. L. Ruzzo",
 	title = "The iterated mod problem",
 	journal = IC,
 	volume = 80,
 	pages = "193-204",
 	year = 1989}

@incollection{Collins&Mignotte&Winkler:1982,
	key = "G. Collins, Mignotte, and Winkler 1982",
	author = "G. E. Collins and M. Mignotte and F. Winkler",
  	title = "Arithmetic in basic algebraic domains",
  	booktitle = "Computer Algebra: Symbolic and Algebraic Computation",
  	editor = "B. Buchberger and G. E. Collins and R. Loos",
  	publisher = SV,
  	year = 1982,
  	pages = "189-220"}

@book{Knuth:1981,
  	key = "Knuth 1981",
  	author = "D. E. Knuth",
  	title = "The Art of Computer Programming. Volume 2: Seminumerical
		 Algorithms",
  	publisher = AW,	
  	year = 1981,
	note = "2nd edition"}

@article{Chernoff:1952,
	key = "Chernoff 1952",
	author = "H. Chernoff",
	title = "A measure of asymptotic efficiency for 
		 tests of a hypothesis based on the sum of observations",
	journal = ANMS,
	volume = 23,
	pages = "493-507",
	year = 1952
	}

@article{Post:1944,
	key = "Post 1944",
	author = "E. L. Post",
	title = "Recursively enumerable sets of positive integers
		 and their decision problems",
	journal = BAMS,
	volume = 50,
	pages = "284-316",
	year = 1944
	}

@techreport{Comba:1989,
  	key = "Comba 1989",
  	author = "P. G. Comba",
  	title = "Experiments in fast multiplication of large integers",
  	institution = "IBM, Cambridge Scientific Center",
  	number = "G320-2158",
  	month = "February",
  	year = 1989}

@article{Pollard:1971a,
	key = "Pollard 1971a",
	author = "J. M. Pollard",
	title = "The fast {F}ourier transform in a finite field",
	journal = MC,
	volume = 25,
	pages = "365-374",
	year = "{\noopsort{1971a}}1971"}

@article{Brassard&Monet&Zuffellato:1986,
	key = "Brassard, Monet, and Zuffellato 1986",
	author = "G. Brassard and S. Monet and D. Zuffellato",
	title = "Algorithmes pour l'arithm{\'e}tique des tr{\`e}s 
	         grands entiers",
	journal = "Techniques et Science Informatique",
	volume = 5,
	pages = "89-102",
	year = 1986
	}

@article{Rabin&Scott:1959,
	key = "Rabin and Scott 1959",
	author = "M. O. Rabin and D. Scott",
  	title = "Finite Automata and their decision problems",
  	journal = IBMJ,
	volume = 3,
  	year = 1959,
  	pages = "115-125"
	}

@incollection{Kuechlin&Lutz&Nevin:1991,
	key = "Kuechlin, Lutz, and Nevin 1991",
	author = "W. Kuechlin and D. Lutz and N. Nevin",
	title = "Integer multiplication in {PARSAC-2} on
stock microprocessors",
	booktitle = AAECC9,
	editor = "H. F. Mattson and T. Mora and T. R. N. Rao",
	publisher = SV,
	series = LNICS,
	volume = 539,
	year = 1991,
	pages = "206-217"}

@article{Kelvin:1901,
	key = "Kelvin 1901",
	author = "Lord Kelvin",
	title = "Nineteenth century clouds over the dynamical theory
of heat and light",
	journal = PMAG,
	volume = 2,
	year = 1901,
	pages = "1-40"}

@incollection{Fagin:1990,
	key = "Fagin 1990",
	author = "B. S. Fagin",
	title = "Large integer multiplication on massively parallel processors",
	booktitle = "Proc. Frontiers '90:  Third Symposium on the Frontiers of
Massively Parallel Computation",
	publisher = IEEEPR,
	year = 1990,
	pages = "38-42"}

@inproceedings{Sipser:1992,
	key = "Sipser 1992",
	author = "M. Sipser",
	title = "The history and status of the {P} versus {NP} question",
	booktitle = STOC92,
	year = 1992,
	publisher = "ACM Press",
	pages = "603-618"}

@article{Bshouty&Mansour&Schieber&Tiwari:1992,
	key = "Bshouty, Mansour, Schieber, and Tiwari 1992",
	author = "N. H. Bshouty and Y. Mansour and B. Schieber and P. Tiwari",
	title = "Fast exponentiation using the truncation operation",
	journal = CC,
	volume = 2,
	year = 1992,
	pages = "244-255"}

@article{Santos:1969,
	key = "Santos 1969",
	author = "E. S. Santos",
	title = "Probabilistic {Turing} machines and computability",
	journal = PAMS,
	volume = 22, 
	year = 1969,
	pages = "704-710"}

@article{Lemoine:1882,
	key = "Lemoine 1882",
	author = "E. Lemoine",
	title = "{D\'ecomposition} d'un nombre entier {$N$} en ses puissances
$n$i\`emes maxima",
	journal = CRASP,
	volume = 95,
	year = 1882,
	pages = "719-722"}

@book{Minsky:1967,
	key = "Minsky 1967",
	author = "M. Minsky",
	title = "Computation:  Finite and Infinite Machines",
	publisher = "Prentice-Hall",
	year = 1967}

@article{Fitch:1974,
	key = "Fitch 1974",
 	author = "J. Fitch",
 	title = "A simple method of taking $n$th roots of integers", 
 	journal = ASB,
 	volume = 8,
 	pages = "26",
 	year = 1974}

@unpublished{BernsteinD:1995,
 	key = "D. Bernstein 1995",
 	author = "D. Bernstein",
 	title = "Detecting perfect powers in essentially linear time",
 	note = "Unpublished manuscript",
 	year = "1995", 
	comment = "Dan says it will be submitted to Math. Comp."}

@book{Motwani&Raghavan:1995,
	key = "Motwani and Raghavan 1995",
	author = "R. Motwani and P. Raghavan",
	title = "Randomized Algorithms",
	publisher = CUP,
	year = 1995}

@article{Karp:1991,
	key = "Karp 1991",
	author = "R. M. Karp",
	title = "An introduction to randomized algorithms",
	journal = DAM,
	volume = 34,
	year = 1991,
	pages = "165-201"}