We introduce the notion of covering complexity of a probabilistic
verifier. The covering complexity of a verifier on a given input is
the minimum number of proofs needed to ``satisfy'' the verifier on
every random string, i.e., on every random string, at least one of the
given proofs must be accepted by the verifier. The covering
complexity of PCP verifiers offers a promising route to getting
stronger inapproximability results for some minimization problems, and
in particular, (hyper)-graph coloring problems. We present a PCP
verifier 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 verifier is a simple Not-all-Equal check
on the four bits it reads. This enables us to prove that for {\em
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.