UR-CS Participating Faculty: Lane A. Hemaspaandra (= Lane A. Hemachandra)
The following is adapted, in part, from a survey on sets of low information content written by Lane Hemaspaandra, Mitsunori Ogihara, and Osamu Watanabe.
In 1977,
Berman and Hartmanis conjectured that
all NP-complete sets
are polynomially isomorphic;
that is, for any two sets
and
that are
-complete for NP,
there exists a polynomial-time computable bijection
such that
and
.
As evidence of the plausibility of their conjecture,
they showed that all then-known NP-complete sets
were indeed polynomially isomorphic.
All then-known (and, for that matter, all currently known)
NP-complete sets are dense;
there exists a constant
such that, for all sufficiently large
,
the set contains at most
elements of
length at most
.
Thus, if the Berman-Hartmanis Conjecture is true,
then
sparse sets--sets with polynomially bounded density--cannot
be NP-complete.
This observation yielded another conjecture:
Sparse sets are not NP-complete.
For this reason,
Hartmanis examined the possibility of
the existence of sparse complete sets
for various complexity classes.
He showed that some classes,
such as PSPACE and EXP,
lack sparse logspace-complete
sets.
He also conjectured that NL and P lack
sparse complete sets under logspace reductions, a
conjecture that this project helped resolve.
The above-mentioned studies motivated researchers to study more broadly the classes of sets whose complete languages could not be reduced to sparse sets unless the classes collapsed, and this is a central focus of this project.
Another motivation for the study of sparse sets is their close
relationship to notions of polynomial-time ``quasi-solvability.''
The class of sets having polynomial-size circuits is exactly
the class
of sets that are polynomial-time Turing reducible to sparse sets (this
is due to A. Meyer). Thus, sets that are
polynomial-time Turing reducible to sparse sets
can be regarded to be polynomial-time solvable, give or
take a small amount of informaiton.
Furthermore, less flexible reducibilities characterize some other
notions of polynomial-time
quasi-solvability.
For example, for a given set
, a polynomial-time algorithm that
correctly answers to the question ``
?'' for all but a
sparse set of
can be considered to be
a good polynomial-time approximation of
.
It is known that the class of sets so
approximable (the P-close sets)
are reducible to sparse sets by truth-table
reductions that only ask one question per input.
Thus, studying
the difference
between various reducibilities to sparse sets
can separate
the analogous notions of polynomial-time quasi-solvability.
For example,
from the fact, due to Book and Ko, that
the 1-truth-table
reducibility to sparse sets
is strictly weaker than
the
-reducibility to sparse sets,
we can conclude that
P-close approximations
define a strictly weaker
(that is, closer to actual polynomial-time solvability)
polynomial-time quasi-solvability notion
than polynomial-size cuicuits.
Note that most discussions of quasi-solvability in some way assume that sparseness (either in the set to which as set is reduced, or in the amount by which an approximation fails) is a ``near enough miss'' to be meaningful. One of the issues with which this project is concerned is whether sparse sets in fact are in fact ``not hard.'' The study of reductions to sparse sets, discussed earlier, provides one type of evidence that sparse sets are not hard. Evidence of the weakness of sparse sets also comes from many other quarters, such as lowness theory.
(Last modified: June 5, 2008.)