Average-case complexity has been investigated in various other aspects and a brief survey of these results is presented in this section.
1. NP-Isomorphism Problem with Respect to Random Instances.
The Berman-Hartmanis NP-isomorphism
conjecture [BH77] has provided much of the
impetus for research in structural
complexity theory during the last two decades.
It conjectures that all many-one NP-complete problems are
polynomially isomorphic.
Following the
isomorphism
theory
of Berman and
Hartmanis [BH77], Wang and Belanger [WB95] provided a general framework
for studying the isomorphism problem for NP-complete sets
with respect to random instances.
Let 
and 
be two distributional decision
problems. and are
p-isomorphic if there is a one-one, onto, p-time computable
and invertible reduction 
such that is p-time
reducible to via and is p-time
reducible to via 
.
By Theorem 4.2 it follows that any NP-complete
problem with a flat distribution cannot be p-isomorphic
to DH1.
Write 
if 
and 
.
Let and 
be one-one, p-time computable, and invertible
reductions of to and to ,
respectively, such that 
and 
are
length-increasing. Assume also that 
and
. Then is p-isomorphic to
[WB95][BW93]. Using this result and the Distribution
Controlling Lemma (Lemma 3.3 (2)),
Wang and Belanger [WB95] showed that
all the known average-case NP-complete problems under p-time
reductions are p-isomorphic.
2. Relations to Worst-Case Complexity Classes.
It is not known whether DistNP is included in AP. Results in
this line will be of the form
``
iff ...,"
`` if ...," or something of this nature
unless there is a major breakthrough. The following two results
are of this type and they are related to worst-case complexity
classes.
It was shown in [Boo74] that 
implies
the existence of a tally language 
in 
.
Let 
be proportional to 
. If ,
then 
, which is a contradiction.
Hence, if , then
AP does not include DistNP [BCGL92].
A similar result can also be found
in [Gur91a] under the
assumption that 
.
The following result
shows how P = NP may fail using average-case complexity.
A set is almost in NP with respect to 
if
there is a deterministic Turing machine that accepts in time
, and has a subset 
in NP such that
for some constant 
.
A distributional decision problem 
is
hard on positive instances
if for any deterministic Turing machine
that accepts in time and for any 
,
.
Wang and Belanger [WB93a] showed that
P 
NP if and only if there is
such that is almost in NP
with respect to and is hard on positive instances,
where is exponential-time computable.
3. Problems that Are Easy on Average under a
Set of Distributions.
One may wonder whether there is a set that is
not in P but is in AP under
every p-time computable distribution. A
diagonalization construction
provides an affirmative answer [Sch95a],
but it is not known whether there are natural examples.
If a problem is in AP under every exponential-time
computable distribution, then it has to be in
P [SY96]. As a remark, we note
that no AP problems under p-time computable distributions
are harder on average than
a P problem.
More results on structural properties of the class of sets
that are in AP under every p-time computable distribution
can be found
in [SY96][SY95][Sch95b][KS95], and a connection to the resource bounded measure theory
that was
introduced in [Lut92] (see also [Lut96]) can be found in [Sch96].
A similar approach has also been applied to studying
the class of optimization
problems. Under worst-case complexity,
P = NP implies that
all NP optimization problems are polynomial-time solvable.
Schuler and
Watanabe [SW95] investigated how much of
this
can be carried out in the
average-case setting. They showed that
if every NP decision problem is in AP under every
-samplable distribution, then
every NP optimization problem is solvable in average polynomial time
with respect to every p-time computable distribution, and vice versa.
4. Generating Test Instances for Promise Problems. Suppose one wants to design an algorithm that outputs a satisfying assignment in polynomial time on average if the input is guaranteed to be a satisfiable Boolean formula. The correctness of the algorithm is often justified by testing the algorithm on some randomly generated satisfiable Boolean formulas. Watanabe [Wat94] provided a framework for investigating the difficulty of generating test instances for promise NP search problems and some ``completeness" results were shown based on the known average-case NP-complete problems.
5. Other Complexity Measures. The notion of average polynomial time can be generalized to other complexity measures. Among others, sub-polynomial average time has attracted some attention. Log-space average-case measurement has been investigated in [BCGL92]. Another obvious extension is to study the average-case counterparts of ZPP, BPP, P/poly, etc., using the notion of average polynomial time.
6. Optimization Problems.
We end this list by asking how average-case
complexity may help in obtaining results for actual
optimization problems. Although certain NP optimization
problems cannot have good
approximation solutions in deterministic
polynomial time unless 
(see, e.g.,
[ALMSS92]), exact solutions, or good
approximations, could still be obtained
in average polynomial
time, or some average-case ``completeness" results could be
shown.
Acknowledgment. I thank Leonid Levin for his Complexity Theory Seminar at Boston University in 1987-88; at this seminar, I first learned average-case complexity. I thank Steven Homer for his advice and encouragement. I am grateful to Jay Belanger for many valuable discussions and a careful reading of this paper. I thank Yuri Gurevich, Leonid Levin, and Ramarathnam Venkatesan for a number of recent conversations that have helped shape my view on average-case complexity. I am grateful to all the comments I received on the early drafts of this paper, and in particular, I thank Jay Belanger, Jin-Yi Cai, Yuri Gurevich, Osamu Watanabe, and an anonymous referee for their constructive comments, which have helped improve my presentation. I taught a complexity seminar, based on an early version of this paper, at Zhongshan University, Guangzhou, in June 1996, and I thank Guangkun Hou, Binghuan Zhu, Hong Zhu, and all the other participants for their comments. Finally, I would like to express my gratitude to Lane Hemaspaandra for editing this paper.
