×

zbMATH — the first resource for mathematics

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

MSC:
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