|
Abstract : |
We introduce the notion of covering complexity of a verier for probabilistically checkable proofs (PCP). Such a verier is given an input, a claimed theorem, and an oracle, representing a purported proof of the theorem. The verier is also given a random string and decides whether to accept the proof or not, based on the given random string. We dene the covering complexity of such a verier, on a given input, to be the minimum number of proofs needed to \satisfy " the veri er on every random string, i.e., on every random string, at least one of the given proofs must be accepted by the verier. The covering complexity of PCP veriers oers a promising route to getting stronger inapproximability results for some minimization problems, and in particular, (hyper-)graph coloring problems. We present a PCP verier for NP statements that queries only four bits and yet has a covering complexity of one for true statements and a super-constant covering complexity for statements not in the language. Moreover, the acceptance predicate of this verier is a simple Not-all-Equal check on the four bits it reads. This enables us to prove that for any constant c, it is NP-hard to color a 2-colorable 4-uniform hypergraph using just c colors, and also yields a super-constant inapproximability result under a stronger hardness assumption., |
