Hartmanis, J. Structural complexity column - Sparse complete sets of NP and the optimal collapse of the polynomial hierarchy. (English) Zbl 0661.68046 Bull. EATCS 32, 73-81 (1987). 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 Cited in 1 Document MSC: 68Q25 Analysis of algorithms and problem complexity 68Q05 Models of computation (Turing machines, etc.) (MSC2010) 03D15 Complexity of computation (including implicit computational complexity) Keywords:polynomial time hierarchy; sparse NP-complete sets; survey PDFBibTeX XMLCite \textit{J. Hartmanis}, Bull. EATCS 32, 73--81 (1987; Zbl 0661.68046)