zbMATH — the first resource for mathematics

A new multilayered PCP and the hardness of hypergraph vertex cover. (English) Zbl 1079.68039

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C65 Hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX Cite
Full Text: DOI