×

zbMATH — the first resource for mathematics

Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. (English) Zbl 1293.68132
Proceedings of the 42nd annual ACM symposium on theory of computing, STOC ’10. Cambridge, MA, USA, June 5–8, 2010. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-817-9). 251-260 (2010).

MSC:
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C65 Hypergraphs
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI