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 NPcomplete sets
are polynomially isomorphic;
that is, for any two sets and
that are
complete for NP,
there exists a polynomialtime computable bijection
such that
and
.
As evidence of the plausibility of their conjecture,
they showed that all thenknown NPcomplete sets
were indeed polynomially isomorphic.
All thenknown (and, for that matter, all currently known)
NPcomplete 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 BermanHartmanis Conjecture is true,
then
sparse sets—sets with polynomially bounded density—cannot
be NPcomplete.
This observation yielded another conjecture:
Sparse sets are not NPcomplete.
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 logspacecomplete
sets.
He also conjectured that NL and P lack
sparse complete sets under logspace reductions, a
conjecture that this project helped resolve.
The abovementioned 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 polynomialtime “quasisolvability.”
The class of sets having polynomialsize circuits is exactly
the class
of sets that are polynomialtime Turing reducible to sparse sets (this
is due to A. Meyer). Thus, sets that are
polynomialtime Turing reducible to sparse sets
can be regarded to be polynomialtime solvable, give or
take a small amount of informaiton.
Furthermore, less flexible reducibilities characterize some other
notions of polynomialtime
quasisolvability.
For example, for a given set , a polynomialtime algorithm that
correctly answers to the question “?” for all but a
sparse set of
can be considered to be
a good polynomialtime approximation of .
It is known that the class of sets so
approximable (the Pclose sets)
are reducible to sparse sets by truthtable
reductions that only ask one question per input.
Thus, studying
the difference
between various reducibilities to sparse sets
can separate
the analogous notions of polynomialtime quasisolvability.
For example,
from the fact, due to Book and Ko, that
the 1truthtable
reducibility to sparse sets
is strictly weaker than
the reducibility to sparse sets,
we can conclude that
Pclose approximations
define a strictly weaker
(that is, closer to actual polynomialtime solvability)
polynomialtime quasisolvability notion
than polynomialsize cuicuits.
Note that most discussions of quasisolvability 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 lowdensity sets cannot be
1truthtable hard for such complexity classes as NP is that no ptime
heuristic algorithm can have a lowdensity symmetric difference with
any NPhard set unless shocking complexity class collapses occur (see
[7]
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 papers, from or related to this project,
by University of Rochester authors. Links to essentially all Lane's
conference and journal papers (and also his arXiv.org technical reports) can
be found via the pointers from the related entries within
Lane's entry at the DBLP
project.
Additionally, here is a link to Lane's complete
publication list
(note: that
list does not itself have links to papers).
 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

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. AmbosSpies, S. Homer, and U. Schöning, editors, Complexity Theory, pages 1–45. Cambridge University Press, 1993.
 4

J.Y. Cai, V. Chakaravarthy, L. Hemaspaandra, and M. Ogihara.
Competing provers yield improved Karp–Lipton collapse results.
Information and Computation, 198(1):1–23, 2005.
 5

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.
 6

G. Erdélyi, L. Hemaspaandra, J. Rothe, and H. Spakowski.
Generalized juntas and NPhard sets.
Theoretical Computer Science, 410(38–40):3995–4000, 2009.
 7

P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
The complexity of manipulative attacks in nearly singlepeaked
electorates.
Artificial Intelligence, 207:69–99, 2014.
 8

P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
The complexity of manipulative attacks in nearly singlepeaked
electorates.
In Proceedings of the 24th International Joint Conference on
Artificial Intelligence, pages 4178–4182. AAAI Press, July/August 2015.
 9

P. Faliszewski and L. Hemaspaandra.
Advice for semifeasible sets and the complexitytheoretic
cost(lessness) of algebraic properties.
International Journal of Foundations of Computer Science,
16(5):913–928, 2005.
 10

P. Faliszewski and L. Hemaspaandra.
Open questions in the theory of semifeasible computation.
SIGACT News, 37(1):47–65, 2006.
 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

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.
 14

L. Hemachandra and R. Rubinstein.
Separating complexity classes with tally oracles.
Theoretical Computer Science, 92(2):309–318, 1992.
 15

E. Hemaspaandra, L. Hemaspaandra, and C. Menton.
Search versus decision for election manipulation problems.
In Proceedings of the 30th Annual Symposium on Theoretical
Aspects of Computer Science, pages 377–388. Leibniz International
Proceedings in Informatics (LIPIcs) #20, February/March 2013.
 16

E. Hemaspaandra, L. Hemaspaandra, and C. Menton.
Search versus decision for election manipulation problems.
ACM Transactions on Computation Theory, 12(#1,
Article 3):1–42, 2020.
 17

E. Hemaspaandra, L. Hemaspaandra, and H. Schnoor.
A control dichotomy for pure scoring rules.
In Proceedings of the 28th AAAI Conference on Artificial
Intelligence, pages 712–720. AAAI Press, July 2014.
 18

E. Hemaspaandra, L. Hemaspaandra, H. Spakowski, and O. Watanabe.
The robustness of LWPP and WPP, with an application to graph
reconstruction.
In Proceedings of the 43rd International Symposium on
Mathematical Foundations of Computer Science, pages 51:1–51:14. Leibniz
International Proceedings in Informatics (LIPIcs) #117, August 2018.
 19

E. Hemaspaandra, L. Hemaspaandra, H. Spakowski, and O. Watanabe.
The robustness of LWPP and WPP, with an application to graph
reconstruction.
Computational Complexity, 29(2, Article 7):1–49, 2020.
 20

L. Hemaspaandra.
Beautiful structures: An appreciation of the contributions of Alan
Selman.
SIGACT News, 45(3):54–70, 2014.
 21

L. Hemaspaandra.
Complexity classes.
In K. Rosen, editor, Handbook of Discrete and Combinatorial
Mathematics, pages 1308–1314. CRC Press, 2nd edition, 2018.
 22

L. Hemaspaandra.
The power of selfreducibility: Selectivity, information, and
approximation.
In D.Z. Du and J. Wang, editors, Complexity and Approximation,
pages 19–47. Springer, 2020.
 23

L. Hemaspaandra.
Juris Hartmanis (1928–2022): Understanding time, space, and
human creativity.
SIGACT News, 53(3):42–45, 2022.
 24

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.
 25

L. Hemaspaandra and D. Narváez.
The opacity of backbones.
In Proceedings of the 31st AAAI Conference on Artificial
Intelligence, pages 3900–3906. AAAI Press, February 2017.
 26

L. Hemaspaandra and D. Narváez.
Existence versus exploitation: The opacity of backbones and
backdoors under a weak assumption.
In Proceedings of the 45th International Conference on Current
Trends in Theory and Practice of Computer Science, pages 247–259.
SpringerVerlag Lecture Notes in Computer Science #11376, January 2019.
 27

L. Hemaspaandra and D. Narváez.
Existence versus exploitation: The opacity of backdoors and
backbones.
Progress in Artificial Intelligence, 10(3):297–308, 2021.
 28

L. Hemaspaandra and D. Narváez.
The opacity of backbones.
Information and Computation, 281(Article 104772):1–10, 2021.
 29

L. Hemaspaandra, M. Ogihara, and S. Toda.
Spaceefficient recognition of sparse selfreducible languages.
Computational Complexity, 4(3):262–296, 1994.
 30

L. Hemaspaandra and J. Rothe.
Unambiguous computation: Boolean hierarchies and sparse
Turingcomplete sets.
SIAM Journal on Computing, 26(3):634–653, 1997.
 31

L. Hemaspaandra and R. Silvestri.
Easily checked generalized selfreducibility.
SIAM Journal on Computing, 24(4):840–858, 1995.
 32

L. Hemaspaandra and L. Torenvliet.
Optimal advice.
Theoretical Computer Science, 154(2):367–377, 1996.
 33

L. Hemaspaandra and L. Torenvliet.
Pselectivity, 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.
SpringerVerlag Lecture Notes in Computer Science #3881, January 2006.
 34

L. Hemaspaandra and R. Williams.
An atypical survey of typicalcase heuristic algorithms.
SIGACT News, 43(4):71–89, 2012.
(Last modified: February 16, 2023.)
Lane A. Hemaspaandra
