×

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 XML Cite
Full Text: DOI