References

ALMSS92

S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. In Proceedings of the 33rd Symposium on Foundations of Computer Science, IEEE Computer Society Press, pages 14-23, 1992.

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 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 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 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. (Preliminary version appeared in Proceedings of the 21st Symposium on Theory of Computing, ACM Press, pages 204-216, 1989.)

BH77

L. Berman and J. Hartmanis. On isomorphisms and density of NP and other complete sets. SIAM Journal on Computing, 6:305-321, 1977.

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-18, 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.

Boo74

R. Book. Tally languages and complexity classes. Information and Control, 26:213-229, 1974.

CS95

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.

Gac74

P. Gács. On the symmetry of algorithmic information. Soviet Mathematics Doklady, 15:1477-1481, 1974.

GHS91

J. Geske, D. Huynh, and J. Seiferas. A note on almost-everywhere complex sets with application to polynomial complexity degrees. Information and Computation, 92:97-104, 1991.

GGH94

M. Goldmann, P. Grape, and J. Håstad. On average time hierarchies. Information Processing Letters, 49:15-20, 1994.

Gur87

Y. Gurevich. Complete and incomplete randomized NP problems. In Proceedings of the 28th 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. EATCS Bulletin, pages 112-121, 1989. It has been reprinted in Current Trends in Theoretical Computer Science (G. Rozenberg and A. Salomaa eds), World Scientific, pages 245-253, 1993.

Gur91a

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 International Colloquium on Automata, Languages and Programming, vol 510 of Lecture Notes in Computer Science, Springer-Verlag, pages 615-628, 1991.

GS87

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

Har11

G. Hardy. Properties of logarithmico-exponential functions. Proceedings of London Mathematical Society, 10:54-90, 1911.

Har24

G. Hardy. Orders of Infinity, The ``infinitärcalcül'' of Paul du Bois-Reymond. Vol. 12 of Cambridge Tracts in Math. & Mathematical Physics. Cambridge University Press, 1924.

HS65

J. Hartmanis and R. Stearns. On the computational complexity of algorithms. Trans. Amer. Math. Soc., 117:285-306, 1965.

Imp95

R. Impagliazzo. A personal view of average-case complexity. In Proceedings of the 10th Conference on Structure in Complexity Theory, IEEE Computer Society Press, pages 134-147, 1995.

IL90

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

Joh84

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

Jon93

N. Jones. Constant time factors do matter. In Proceedings of the 25th Symposium on Theory of Computing, ACM Press, pages 602-611, 1993.

KS95

C. Karg and R. Schuler. Structure in average case complexity. In Proceedings of the 6th International Symposium on Algorithms and Computation, vol 1004 of Lecture Notes in Computer Science, Springer-Verlag, pages 62-71, 1995.

Ko83

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

Kob95

K. Kobayashi. Transformations that preserve malignness of universal distributions. In Proceedings of the 1st International Computing and Combinatorics Conference, vol 959 of Lecture Notes in Computer Science, Springer-Verlag, pages 420-429, 1995.

Lev86

L. Levin. Average case complete problems. SIAM Journal on Computing, 15:285-286, 1986. (Preliminary version 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.

LV92

M. Li and P. Vitányi. Average case complexity under the universal distribution equals worst-case complexity. Information Processing Letters, 42:145-149, 1992.

Lut92

J. Lutz. Almost everywhere high nonuniform complexity. Journal of Computer and System Sciences, 44:220-258, 1992.

Lut96

J. Lutz. The quantitative structure of exponential time. In Complexity Theory Retrospective II (L. Hemaspaandra and A. Selman eds), Springer-Verlag, this volume.

Mil91

P. Miltersen. The complexity of malign ensembles. In Proceedings of the 6th Conference on Structure in Complexity Theory, IEEE Computer Society Press, pages 164-171, 1991.

PPST83

W. Paul, N. Pippenger, E. Szemerédi, and W. Trotter. On determinism versus nondeterminism and related problems. In Proceedings of the 24th Symposium on Foundations of Computer Science, IEEE Computer Society Press, pages 429-438, 1983.

RS93

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

Sch95a

R. Schuler. Some properties of sets tractable under every polynomial-time computable distribution. Information Processing Letters, 55:179-184, 1995.

Sch95b

R. Schuler. Average polynomial time is hard for exponential time under SN-reductions. In Proceedings of the 15th Conference on the Foundations of Software Technology and Theoretical Computer Science, vol 1026 of Lecture Notes in Computer Science, Springer-Verlag, pages 240-247, 1995.

Sch96

R. Schuler. Truth-table closure and Turing closure of average polynomial time have different measures in EXP. In Proceedings of the 11th Conference on Computational Complexity, IEEE Computer Society Press, 1996, pages 190-195.

SW95

R. Schuler and O. Watanabe. Towards average-case complexity analysis of NP optimization problems. In Proceedings of the 10th Conference on Structure in Complexity Theory, IEEE Computer Society Press, pages 148-159, 1995.

SY95

R. Schuler and T. Yamakami. Sets computable in polynomial time on average. In Proceedings of the 1st International Computing and Combinatorics Conference, vol 959 of Lecture Notes in Computer Science, Springer-Verlag, pages 400-409, 1995.

SY96

R. Schuler and T. Yamakami. Structural average case complexity. Journal of Computer and System Sciences, 52:308-327, 1996. (Preliminary version appeared in Proceedings of the 12th Conference on the Foundations of Software Technology and Theoretical Computer Science, vol. 652 of Lecture Notes in Computer Science, Springer-Verlag, pages 128-139, 1992.)

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 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 Symposium on Theory of Computing, ACM Press, pages 632-642, 1992.

Wan95a

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

Wan95b

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

Wan97

J. Wang. Average-case intractable NP problems. In Advances in Complexity and Algorithms (D.-Z. Du and K.-I. Ko eds), Kluwer Academic Publishers. 1997, to appear.

WB93a

J. Wang and J. Belanger. On average-P vs. average-NP. In Complexity Theory-Current Research (K. Ambos-Spies, S. Homer, and U. Schönings eds.), pages 47-67. Cambridge University Press, 1993. (Preliminary version appeared in Proceedings of the 7th 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.

Wat94

O. Watanabe. Test instance generation for promised NP search problems. In Proceedings of the 9th Conference on Structure in Complexity Theory, IEEE Computer Society Press, pages 205-216, 1994.

Wil84

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

Yam96

T. Yamakami. Polynomial-time samplable distributions. In Proceedings of the 21st International Symposium on Mathematical Foundation of Computer Science, Sept. 1996, to appear.