Three‐query PCPs with perfect completeness over non‐Boolean domains

We study non‐Boolean PCPs that have perfect completeness and query three positions in the proof. For the case when the proof consists of values from a domain of size d for some integer constant d ≥ 2, we construct a nonadaptive PCP with perfect completeness and soundness d −1 + d −2 + ϵ, for any constant ϵ > 0, and an adaptive PCP with perfect completeness and soundness d −1 + ϵ, for any constant ϵ > 0. The latter PCP can be converted into a nonadaptive PCP with perfect completeness and soundness d −1 + ϵ, for any constant ϵ > 0, where four positions are read from the proof. These results match the best known constructions for the case d = 2 and our proofs also show that the particular predicates we use in our PCPs are nonapproximable beyond the random assignment threshold. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005