SIGACT news complexity theory column 34
Lane A. Hemaspaandra · ACM SIGACT News · 2001
This issue's guest columnists are angels. The column was faced with a last-minute cancellation, and they prepared on very short notice a wonderful column. And I'm sure that many readers of the column will want to learn even more by, for example, reading their monograph Complexity Classifications of Boolean Constraint Satisfaction Problems [7].Future complexity columns include Holzer/McKenzie on a familiar complexity class turning up in a surprising context, Gasarch (and a host of contributors) on the future of NP, Schaeffer/Umans on completeness for higher levels of the polynomial hierarchy, Nickelsen/Tantau on partial information classes, and Paturi on the complexity of k -SAT,Regarding the Schaeffer/Umans column, their 2-part column will be in part a kind of Garey and Johnson for completeness results for ∑ i p and π i p , i ≥ 2. You can help their project by, if you have proven natural sets complete for NP NP , coNP NP , NP NP NP , coNP NP NP , etc., letting them ([email protected] and [email protected]) know of your result and its best citation location. Thanks!