@inproceedings{Greenberg&Weiss:1984,
	key = "Greenberg and Weiss 1984",
	author = "A. G. Greenberg and A. Weiss",
	title = "A lower bound for probabilistic algorithms for finite
	state machines",
	booktitle = FOCS84,
	year = 1984,
	pages = "323-331"}

@inproceedings{Freivalds:1981,
	key = "Freivalds 1981",
	author = "R. Freivalds",
	title = "Probabilistic two-way machines",
	booktitle = "Proc. Int. Symp. Math. Found. Comp. Sci.",
	editor = "J. Gruska and M. Chytil",
	series = LNICS,
	volume = 118,
	year = 1981,
	publisher = SV,
	pages = "33-45"}
	
@article{Turing:1936,
	key = "Turing 1936",
	author = "A. M. Turing",
	title = "On computable numbers, with an application to the
{Entscheidungsproblem}",
	journal = PLMS,
	volume = 42,
	year = 1936,
	pages = "230-265",
	comment = "For corrigenda, see {\bf 43} (1937) 544-546"}

@article{Kleene:1987,
	key = "Kleene 1987",
	author = "S. C. Kleene",
	title = "Reflections on {Church's} thesis",
	journal = NDJFL,
	volume = 28,
	year = 1987,
	pages = "490-498"}

@article{Davis:1973,
	key = "M. Davis 1973",
	author = "M. Davis",
	title = "Hilbert's tenth problem is unsolvable",
	journal = AMM,
	volume = 80,
	year = 1973,
	pages = "233-269"}

@book{Davis:1965,
	key = "M. Davis 1965",
	author = "M. Davis",
	title = "The Undecidable",
	publisher = "Raven Press",
	address = NY,
	year = 1965}

@article{Knuth:1976a,
	key = "Knuth 1976a",
	author = "D. E. Knuth",
	title = "Big omicron and big omega and big theta",
	journal = SIGACT,
	volume = 8,
	number = 2,
	year = 1976,
	month = "Apr.-June",
	pages = "18-24"}

@article{Plaisted:1978,
	key = "Plaisted 1978",
	author = "D. A. Plaisted",
	title = "Some polynomial and integer divisibility problems are
{$NP$-hard}",
	journal = SIAMJC,
	volume = 7,
	year = 1978,
	pages = "458-464"}

@article{Plaisted:1984,
	key = "Plaisted 1984",
	author = "D. A. Plaisted",
	title = "New {$NP$-hard} and {$NP$-complete} polynomial and
integer divisibility problems",
	journal = TCS,
	volume = 31,
	year = 1984,
	pages = "125-138"}

@article{Plaisted:1977,
	key = "Plaisted 1977",
	author = "D. A. Plaisted",
	title = "Sparse complex polynomials and polynomial reducibility",
	journal = JCSS,
	volume = 14,
	year = 1977,
	pages = "210-221"}

@article{Heath:1990,
	key = "L. Heath 1990",
	author = "L. S. Heath",
	title = "Covering a set with arithmetic progressions is
		 {NP}-complete",
	journal = IPL,
	volume = 34,
	year = 1990,
	pages = "293-298"}

@techreport{Stockmeyer:1976,
	author = "L. J. Stockmeyer",
	key = "Stockmeyer 1976",
	title = "Arithmetic versus {B}oolean operations in idealized
		 register machines",
	institution = "Math. Dept., IBM Thomas J. Watson Research Center",
	number = "RC 5954",
	year = 1976,
	month = "January"}

@article{Fraenkel&Yesha:1979,
	key = "Fraenkel and Yesha 1979",
	author = "A. S. Fraenkel and Y. Yesha",
	title = "Complexity of problems in games, graphs and algebraic
		 equations",
	journal = DAM,
	volume = 1,
	year = 1979,
	pages = "15-30"}


@article{Fraenkel&Yesha:1980,
	key = "Fraenkel and Yesha 1980",
	author = "A. S. Fraenkel and Y. Yesha",
	title = "Complexity of solving algebraic equations",
	journal = IPL,
	volume = 10,
	year = 1980,
	pages = "178-179"}

@article{Plaisted:1985,
	key = "Plaisted 1985",
	author = "D. A. Plaisted",
	title = "Complete divisibility problems for slowly utilized
oracles",
	journal = TCS,
	volume = 35,
	year = 1985,
	pages = "245-260"}

@article{Michel:1992,
	key = "Michel 1992",
	author = "P. Michel",
	title = "A survey of space complexity",
	journal = TCS,
	volume = 101,
	year = 1992,
	pages = "99-132"}