References

AM75

L. Adleman and K. Manders. The computational complexity of decision procedures for polynomials. In Proceedings of the 16th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, pages 169-177, 1975.

AM76

L. Adleman and K. Manders. Diophantine complexity. In Proceedings of the 17th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, pages 81-88, 1976.

BES80

L. Babai, P. Erdos, and M. Selkow. Random graph isomorphism. SIAM Journal on Computing, 9:628-635, 1980.

BW

J. Belanger and J. Wang. No NP problems averaging over ranking of distributions are harder. Theoretical Computer Science, to appear.

BW93

J. Belanger and J. Wang. Isomorphisms of NP-complete problems on random instances. In Proceedings of the 8th Annual Conference on Structure in Complexity Theory, IEEE Computer Society Press, pages 65-74, 1993.

BW95

J. Belanger and J. Wang. Rankable distributions do not provide harder instances than uniform distributions. In Proceedings of the 1st Annual International Computing and Combinatorics Conference, vol. 959 of Lecture Notes in Computer Science, Springer-Verlag, pages 410-419, 1995.

BW96

J. Belanger and J. Wang. Reductions and convergence rates of average time. In Proceedings of the 2nd Annual International Computing and Combinatorics Conference, vol. 1090 of Lecture Notes in Computer Science, Springer-Verlag, pages 300-309, 1996.

BCGL92

S. Ben-David, B. Chor, O. Goldreich, and M. Luby. On the theory of average case complexity. Journal of Computer and System Sciences, 44:193-219, 1992. (First appeared in Proceedings of the 21st Annual Symposium on Theory of Computing, ACM Press, pages 204-216, 1989.)

BG91

A. Blass and Y. Gurevich. On the reduction theory for average-case complexity. In Proceedings of the 4th Workshop on Computer Science Logic, vol. 533 of Lecture Notes in Computer Science, Springer-Verlag, pages 17-30, 1991.

BG93

A. Blass and Y. Gurevich. Randomizing reductions of search problems. SIAM Journal on Computing, 22:949-975, 1993.

BG95

A. Blass and Y. Gurevich. Matrix transformation is complete for the average case. SIAM Journal on Computing, 24:3-29, 1995.

Bol85

B. Bollobás, Random Graphs, Academic Press, 1985.

BO93

R. Book and F. Otto. String-Rewriting Systems. Springer-Verlag, 1993.

Boo59

W. Boone. The word problem. Annals of Mathematics, 70:207-265, 1959.

CFKL94

J.-Y. Cai, W. Fuchs, D. Kozen, and Z. Liu. Efficient average-case algorithms for the modular group. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, pages 143-152, 1994.

CS96

J.-Y. Cai and A. Selman. Fine separation of average time complexity classes. In Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science, vol 1046 of Lecture Notes in Computer Science, Springer-Verlag, pages 331-343, 1996.

Coo71

S. Cook. The complexity of theorem-proving procedures. In Proceedings of the 3rd Annual Symposium on Theory of Computing, ACM Press, pages 151-158, 1971.

CLR90

T. Cormen, C. Leiserson, and R. Rivest. Introduction to Algorithms, MIT Press and McGraw-Hill, 1990.

Dav77

M. Davis, Unsolvable problems. In Jon Barwise, editor, Handbook of Mathematical Logic, pages 567-594, North-Holland, 1977.

DPR61

M. Davis, H. Putnam, and J. Robinson. The decision problem for exponential diophantine equations. Annals of Math. Series, 74:425-436, 1961.

Deh11

M. Dehn. Über unendliche diskontinuíerliche gruppen. Math. Ann., 71:73-77, 1911.

GJ79

M. Garey and D. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, 1979.

Gur87

Y. Gurevich. Complete and incomplete randomized NP problems. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, pages 111-117, 1987.

Gur89

Y. Gurevich. The challenger-solver game: variations on the theme of P =? NP. Bulletin of the European Association for Theoretical Computer Science, pages 112-121, 1989. Reprinted in G. Rozenberg and A. Salomaa, editors, Current Trends in Theoretical Computer Science, World Scientific, pages 245-253, 1993.

Gur90

Y. Gurevich. Matrix decomposition problem is complete for the average case. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, pages 802-811, 1990.

Gur91

Y. Gurevich. Average case completeness. Journal of Computer and System Sciences, 42:346-398, 1991.

Gur91b

Y. Gurevich. Average case complexity. In Proceedings of the 18th Annual Colloquium on Automata, Languages and Programming, vol. 510 of Lecture Notes in Computer Science, Springer-Verlag, pages 615-628, 1991.

Gur96

Y. Gurevich. Private communication.

GS87

Y. Gurevich and S. Shelah. Expected computation time for Hamiltonian path problem. SIAM Journal on Computing, 16:486-502, 1987.

Ike58

N. Ikeno. A six-symbol ten-state universal Turing machine. In Proceedings of Institute of Electrical Communications, Tokyo, 1958.

IL90

R. Impagliazzo and L. Levin. No better ways to generate hard NP instances than picking uniformly at random. In Proceedings of the 31th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, pages 812-821, 1990.

HW88

G. Hardy and E. Wright. Introduction to the Theory of Numbers, Oxford University Press, 1988.

Joh84

D. Johnson. The NP-completeness column: an ongoing guide. Journal of Algorithms, 5:284-299, 1984.

JM91

J. Jones and Y. Matijasevi(c). Proof of recursive unsolvability of Hilbert's tenth problem. American Mathematical Monthly, 98:689-709, 1991.

Kar72

R. Karp. Reducibility among combinatorial problems. In R. Miller and J. Thatcher, editors, Complexity of Computer Computation, Plenum Press, New York, pages 85-103, 1972.

Knu73

D. Knuth. The Art of Computer Programming, Vol. 1, 2nd ed., Addison-Wesley, 1973.

Ko83

K. Ko. On the definition of some complexity classes of real numbers. Mathematical Systems Theory, 16:95-109, 1983.

Lev73

L. Levin. Universal sorting problems. Problemy Peredaci Informacii (in Russian), 9:115-116, 1973. English translation in Problems of Information Transmission, 9:265-266.

Lev86

L. Levin. Average case complete problems. SIAM Journal on Computing, 15:285-286, 1986. (First appeared in Proceedings of the 16th Symposium on Theory of Computing, ACM Press, page 465, 1984.)

LP81

H. Lewis and C. Papadimitriou. Elements of the Theory of Computation. Prentice-Hall, 1981.

Liu68

C.L. Liu. Introduction to Combinatorial Mathematics. McGraw-Hill, 1968.

MS95

J. Makowsky and A. Sharell. On average case complexity of SAT for symmetric distribution. Journal of Logic Computation, 5:71-92, 1995.

MA78

K. Manders and L. Adleman. NP-complete decision problems for binary quadratics. Journal of Computer and System Sciences, 16:168-184, 1978.

Mar54

A. Markov. Theory of Algorithms, Academy of Sciences of the USSR, Moscow, 1954.

Mar58

A. Markov. On the problem of representability of matrices. Z. Math. Logik Grundlagen Math (in Russian), 4:157-168, 1958.

Mat70

Y. Matijasevic. Enumerable sets are diophantine. Doklady Akademii Nauk SSSR (in Russian), 191:279-282, 1970. English translation with addendum, Soviet Mathematics: Doklady, 11:354-357, 1970.

Min67

M. Minsky. Computation: Finite and Infinite Machines, Prentice Hall, 1967.

Nov55

P. Novikov. On the algorithmic unsolvability of the word problem in group theory. Trudy Mat. Inst. Steklov 44, 143(1955). English text in Russian Translations, 9(1958).

Pra75

V. Pratt. Every prime has a succinct certificate. SIAM Journal on Computing, 4:214-220, 1975.

Pre79

L. Priese. Towards a precise characterization of complexity of universal and non-universal Turing machines. SIAM Journal on Computing, 8:507-523, 1979.

RS93

R. Reischuk and C. Schindelhauer. Precise average case complexity. In Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer, vol. 665 of Lecture Notes in Computer Science, Springer-Verlag, pages 650-661, 1993.

Rot88

J. Rotman. The Theory of Groups, 3rd Edition. Wm. C. Brown Publishers., 1988.

Sha56

C. Shannon. A universal Turing machine with two internal states. In C. Shannon and J. McCarthy, editors, Automata Studies, Princeton University Press, pages 157-166, 1956.

Ste69

B. Stewart. Theory of Numbers, 2nd ed., The Macmillan Company, New York, 1969.

Thu14

A. Thue. Problems über Veränderungen von Zeihenreihen nach gegebenen Regeln. Skr. utzit av Vid Kristiania, I. Mat.-Naturv. Klasse, 10(1914).

Ven91

R. Venkatesan. Average-Case Intractability. Ph.D. Thesis (Advisor: L. Levin), Boston University, 1991.

VL88

R. Venkatesan and L. Levin. Random instances of a graph coloring problem are hard. In Proceedings of the 20th Annual Symposium on Theory of Computing, ACM Press, pages 217-222, 1988.

VR92

R. Venkatesan and S. Rajagopalan. Average case intractability of diophantine and matrix problems. In Proceedings of the 24th Annual Symposium on Theory of Computing, ACM Press, pages 632-642, 1992.

Wae35

B. Vander Waerden. Gruppen von Linearen Transformationen, Ergebnisse Math., IV.2, Springer-Verlag, Berlin, 1935.

Wan96

J. Wang. Average-case computational complexity theory. In L. Hemaspaandra and A. Selman , editors, Complexity Theory Retrospective II, Springer-Verlag, to appear in 1996.

Wan95a

J. Wang. Average-case completeness of a word problem for groups. In Proceedings of the 27th Annual Symposium on Theory of Computing, ACM Press, pages 325-334, 1995.

Wan95b

J. Wang. Random instances of bounded string rewriting are hard. Journal of Computing and Information, Vol. 1, No. 1, Special Issue: Proceedings of the 7th Annual International Conference on Computing and Information, pages 11-23, 1995.

WB93a

J. Wang and J. Belanger. On average-P vs. average-NP. In K. Ambos-Spies, S. Homer, and U. Schönings, editors, Complexity Theory-Current Research, pages 47-67. Cambridge University Press, 1993. (First appeared in Proceedings of the 7th Annual Conference on Structure in Complexity Theory, IEEE Computer Society Press, pages 318-326, 1992.)

WB93b

J. Wang and J. Belanger. Honest iteration schemes of randomizing algorithms. Information Processing Letters, 45:275-278, 1993.

WB95

J. Wang and J. Belanger. On the NP-isomorphism problem with respect to random instances. Journal of Computer and System Sciences, 50:151-164, 1995.

Wat61

S. Watanabe. Five-symbol eight-state and five-symbol six-state Turing machines. Journal of the Association for Computing Machinery, 8:476-483, 1961.

Wil84

H. Wilf. An O(1) expected time algorithm for the graph coloring problem. Information Processing Letters, 18:119-122, 1984.

YK75

A. Yao and D. Knuth. Analysis of the subtractive algorithm for greatest common divisors. In Proceedings of National Academy of Sciences, USA, 72:4720-4722, 1975.