Sets of Low Information Content

UR-CS Participating Faculty: Lane A. Hemaspaandra (= Lane A. Hemachandra)

Project Description

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 $A$ and $B$ that are $\leq_m^p$-complete for NP, there exists a polynomial-time computable bijection $f$ such that $f(A) = B$ and $f(\overline{A}) = \overline{B}$. 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 $c$ such that, for all sufficiently large $n$, the set contains at most $2^{n^c}$ elements of length at most $n$. 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$, a polynomial-time algorithm that correctly answers to the question “$x \in A$?” for all but a sparse set of $x$ can be considered to be a good polynomial-time approximation of $A$. 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 $\leq^p_T$-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 [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).

References

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. Ambos-Spies, 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 NP-hard 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 single-peaked electorates.
Artificial Intelligence, 207:69–99, 2014.

8

P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra.
The complexity of manipulative attacks in nearly single-peaked 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 complexity-theoretic 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 self-reducibility: 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. Springer-Verlag 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.
Space-efficient recognition of sparse self-reducible languages.
Computational Complexity, 4(3):262–296, 1994.

30

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

31

L. Hemaspaandra and R. Silvestri.
Easily checked generalized self-reducibility.
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.
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.

34

L. Hemaspaandra and R. Williams.
An atypical survey of typical-case heuristic algorithms.
SIGACT News, 43(4):71–89, 2012.

$\begin{tabular}{l} {}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\ \hline \end{tabular}$

(Last modified: February 16, 2023.)