|
Sets of Low Information Content
In brief: This project explores the properties of sets of low
information content--especially sparse sets. Particular emphasis is
given to the question of whether sparse sets can be complete for the
fundamental complexity classes, such as NP, via the standard types of
reductions.
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.
Since a consequence of the fact that low-density sets cannot be
1-truth-table hard for such complexity classes as NP is that no p-time
heuristic algorithm can have a low-density symmetric difference with
any NP-hard set unless shocking complexity class collapses occur (see
[19] for a discussion of this,
especially as it applies to why heuristic algorithms cannot do too
well in solving hard problems about election manipulation).
- 1
-
This is a list of selected journal (except when the work has not yet
appeared in journal/book form, plus in some cases some conference articles)
papers, from or related to this project, by University of Rochester authors.
Essentially all the papers listed below can be found, in their full technical
report versions, in the UR-CS Technical Report Archive's
theory section. Here is
Lane's complete publication
list
and links to
essentially all his conference and journal papers (and also his arXiv.org
technical reports) can be found via the ``EE'' (electronic edition) links at
Lane's entry at the DBLP
project.
- 2
-
E. Allender, L. Hemachandra, M. Ogiwara, and O. Watanabe.
Relating equivalence and reducibility to sparse sets.
SIAM Journal on Computing, 21(3):521-539, 1992.
- 3
-
L. Hemachandra, M. Ogiwara, and O. Watanabe.
How hard are sparse sets?
In Proceedings of the 7th Structure in Complexity Theory
Conference, pages 222-238. IEEE Computer Society Press, June 1992.
- 4
-
L. Hemachandra and R. Rubinstein.
Separating complexity classes with tally oracles.
Theoretical Computer Science, 92(2):309-318, 1992.
- 5
-
V. Arvind, Y. Han, L. Hemachandra, J. Köbler, A. Lozano, M. Mundhenk,
M. Ogiwara, U. Schöning, R. Silvestri, and T. Thierauf.
Reductions to sets of low information content.
In K. Ambos-Spies, S. Homer, and U. Schöning, editors,
Complexity Theory, pages 1-45. Cambridge University Press, 1993.
- 6
-
L. Hemaspaandra, M. Ogihara, and S. Toda.
Space-efficient recognition of sparse self-reducible languages.
Computational Complexity, 4(3):262-296, 1994.
- 7
-
L. Hemaspaandra, A. Hoene, A. Naik, M. Ogiwara, A. Selman, T. Thierauf, and
J. Wang.
Nondeterministically selective sets.
International Journal of Foundations of Computer Science,
6(4):403-416, 1995.
- 8
-
L. Hemaspaandra and R. Silvestri.
Easily checked generalized self-reducibility.
SIAM Journal on Computing, 24(4):840-858, 1995.
- 9
-
L. Hemaspaandra and L. Torenvliet.
Optimal advice.
Theoretical Computer Science, 154(2):367-377, 1996.
- 10
-
L. Hemaspaandra and J. Rothe.
Unambiguous computation: Boolean hierarchies and sparse
Turing-complete sets.
SIAM Journal on Computing, 26(3):634-653, 1997.
- 11
-
C. Glaßer and L. Hemaspaandra.
A moment of perfect clarity I: The parallel census technique.
SIGACT News, 31(3):37-42, 2000.
- 12
-
C. Glaßer and L. Hemaspaandra.
A moment of perfect clarity II: Consequences of sparse sets hard
for NP with respect to weak reductions.
SIGACT News, 31(4):39-51, 2000.
- 13
-
J. Cai, V. Chakaravarthy, L. Hemaspaandra, and M. Ogihara.
Competing provers yield improved Karp-Lipton collapse results.
Information and Computation, 198(1):1-23, 2005.
- 14
-
P. Faliszewski and L. Hemaspaandra.
Advice for semifeasible sets and the complexity-theoretic
cost(lessness) of algebraic properties.
International Journal of Foundations of Computer Science,
16(5):913-928, 2005.
- 15
-
P. Faliszewski and L. Hemaspaandra.
Open questions in the theory of semifeasible computation.
SIGACT News, 37(1):47-65, 2006.
- 16
-
L. Hemaspaandra and L. Torenvliet.
P-selectivity, immunity, and the power of one bit.
In Proceedings of the 32nd International Conference on Current
Trends in Theory and Practice of Computer Science, pages 323-331.
Springer-Verlag Lecture Notes in Computer Science #3881, January 2006.
- 17
-
G. Erdélyi, L. Hemaspaandra, J. Rothe, and H. Spakowski.
Frequency of correctness versus average polynomial time.
Information Processing Letters, 109(16):946-949, 2009.
- 18
-
G. Erdélyi, L. Hemaspaandra, J. Rothe, and H. Spakowski.
Generalized juntas and NP-hard sets.
Theoretical Computer Science, 410(38-40):3995-4000, 2009.
- 19
-
P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
The complexity of manipulative attacks in nearly single-peaked
electorates.
In Proceedings of the 13th Conference on Theoretical Aspects of
Rationality and Knowledge, pages 228-237. ACM Digital Library, July 2011.
(Last modified: February 1, 2012.)
Lane A. Hemaspaandra
|