×

zbMATH — the first resource for mathematics

A new multilayered PCP and the hardness of hypergraph vertex cover. (English) Zbl 1192.68290
Proceedings of the thirty-fifth annual ACM symposium on theory of computing (STOC 2003), San Diego, CA, USA,. New York, NY: ACM Press (ISBN 1-58113-674-9). 595-601, electronic only (2003).

MSC:
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
05C65 Hypergraphs
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI