Title: Density and Complexity of Instances in NP-Hard Sets
Speaker: John Hitchcock, University of Wyoming
Date: Wednesday, April 23, 2008 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
There is large body of research in computational complexity about the density of hard and complete sets. This direction was suggested by Berman and Hartmanis (1977) when they showed that all known NP-complete sets are polynomial-time isomorphic. As SAT has exponential density, it follows that all known NP-complete sets are exponentially dense. Is this true for every NP-complete set? An affirmative answer would separate NP from P.
A sparse set is a set with polynomial density. Research has focused on whether hard or complete sets can be sparse. Typical results show that complexity classes collapse if NP has a sparse hard set. For example, Mahaney (1982) showed that P = NP if there is a sparse NP-hard set (hard under many-one reductions). Karp and Lipton (1980) showed that if NP has a Turing-hard sparse set, then the polynomial-time hierarchy collapses to its second level.
While research has focused on polynomial density, all known NP-hard sets are exponentially dense. What collapses occur if NP has a subexponentially-dense hard set? The techniques used for sparse sets only show that NP can be solved in subexponential time. We use a different approach to obtain a collapse of the polynomial-time hierarchy. This result is unusual as we start with a subexponential condition in the hypothesis and obtain a collapse involving only polynomial complexity classes.
Specifically, we show that if there is an NP-hard set with subexponential density, then coNP is contained in NP/poly. In other words, there are polynomial-size proofs for tautologies that can be verified by polynomial-size circuits. Yap (1983) showed that this collapses the polynomial-time hierarchy to its third level. Therefore all NP-hard sets are exponentially dense unless the hierarchy collapses. We also show under the same assumption that all NP-hard sets have exponentially many instances with high instance complexity. These results hold for Turing reductions that make a sublinear number of queries.
Joint work with Harry Buhrman.