×

Structural complexity column - Sparse complete sets of NP and the optimal collapse of the polynomial hierarchy. (English) Zbl 0661.68046

There exists a variety of results concerning the possibilities (and the consequences of) the existence of sparse NP-complete sets (under various types of reducibilities). This paper surveys the most important results along these lines, e.g., there exist (many-one) sparse NP-complete sets if and only if \(P=NP\). Furthermore, there exist sparse (Turing-) NP-hard sets only if \(PH=\Sigma^ p_ 2\), and there exist sparse (Turing-) NP- complete sets only if \(PH=P^{SAT[O(\log n)]}\). The emphasis of this survey is on this last result since it uses a new clever census counting technique.
Reviewer: U.Schöning

MSC:

68Q25 Analysis of algorithms and problem complexity
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
03D15 Complexity of computation (including implicit computational complexity)
PDFBibTeX XMLCite