University of Toronto

Toronto, Ontario

Canada M5S 3G4

In response to this need, L. Levin initiated in 1984 a theory of average-case NP-completeness. Levin's theory deals with average-case NP-complete problems using polynomial-time many-one reductions. The reducibility is a method by which we can classify the distributional NP problems.

In this thesis, we develop a more general theory of average-case complexity to determine the relative complexity of all natural average-case intractable problems. We investigate structure of reducibilities, including a bounded-error probabilistic truth-table reducibility. We introduce a variety of relativizations of fundamental average-case complexity classes of distributional decision problems. These relativizations are essential when we attempt to expand our notion of average polynomial-time computability to develop a hierarchy above average NP problems.

Average-case analyses are very sensitive to the choice of probability distributions. We have observed that if the input probability distribution decays exponentially with size, for instance, all NP-complete problems are solved ``fast'' on the average. This phenomenon does not reflect a significant feature of average-case analysis. This thesis includes a thorough analysis of structural properties of feasibly computable distributions and feasibly samplable distributions.

In addition, one may ask how we can extract the essential average behavior of algorithms independent of the choice of probability distributions. To answer this question, this thesis introduces the new notion of quintessential computability, which expands the boundary of worst-case feasible computability (such as polynomial-time computability), and asserts the invariance of average-case complexity of algorithms regardless of which feasibly computable distributions are chosen. This thesis examines the hardness of this real computability and its structural properties.

I started reading these papers and technical reports and enjoyed discussing Levin's definition of ``polynomial on average'' with Rainer Schuler, who was finishing his thesis on probabilistic computations. The foundations of this thesis were established during this time, and the results were presented at a conference in New Delhi in December, 1992.

In June of 1994, I met Rainer Schuler again at a conference held in Amsterdam. He had with him a paper which solved a problem we had left open in our 1992 paper. We soon started working together, refining his key algorithm to construct hard sets which cannot be computable in feasible time. These results were later presented at a conference in Xi'an, China, in August of 1995 and are also included in this thesis.

This thesis demands of little preparatory knowledge in the theory of computational complexity. Most concepts are thoroughly defined in each section of this thesis or are self-explanatory.

I am extremely grateful to Stephen A. Cook for his hospitality and expert supervision. I thank him also for his direction and support, without which I could not have come to Canada to pursue my Ph.D. degree. My thanks also go to my friend Rainer Schuler who has been my collaborator since I visited the Abteilung Theoretische Informatik of the Universit{"a}t Ulm in 1991. I would like to thank Jie Wang and Osamu Watanabe for helpful comments and fruitful criticism. Special thanks go to Yuri Gurevich and Alan Selman for his kindness and support. I am also indebted to Leonid Levin and Oded Goldreich for helpful comments. I greatly appreciate the input of my thesis committee members, Steve Cook, Allan Borodin, Alasdair Urquhart, Charlie Rackoff, Yuri Gurevich, Anthony J. Bonner, Rudolf Mathon, and Radford Neal.

I thank my friends Brian Nixon and Luis Dissett at the University of Toronto for their kind advice and encouragement. My special thanks also go to Eric Harley and Debby Repka for pointing out typos and grammatical errors in an early manuscript.

My parents, Fujio and Yoshiko, have supported me emotionally and financially during my studies in Toronto. I also thank my grandmother, Nawo, from the bottom of my heart for spiritual guidance. My great appreciation should go to my fiancee Mitsue Nomura who has helped me write this thesis.

Toronto, Canada

May 7, 1997

Submitted in conformity with the requirements

for the Degree of Doctor of Philosophy

Graduate Department of Computer Science

University of Toronto