Is there any natural decision problem that "trivially fits" the definition of a PCP-verifier? I mean, a problem precisely defined as follows: given a set of constraints (each one depending on the values of an unknown bit string at some fix locations, being the number of them constant), find out whether there exists such string satisfying all the constraints ---and we know that, for all problem instances such that this string doesn't exist, at least some fix proportion of the given constraints won't be satisfied, e.g. $\frac{1}{2}$. For instance, the definition of 3SAT does not satisfy the latter condition if the constraints are the disjunctive clauses themselves, as some negative 3SAT instances can be satisfied for all clauses but one.

According to the proof of the PCP theorem for class NP (i.e. $NP = PCP(log$ $n, 1)$), by applying a series of gap amplifications (each one doubling the number of minimum unsatisfied constraints in the negative cases) we can turn any NP problem into a problem fulfilling that condition, although I'm not aware of any concrete problem resulting from this process mentioned in the literature. It seems that, if we want to see any of these problems, then we have to take some NP problem and perform this series of amplifications by hand.

Note that Hastad's 3-bit PCP-verifier is defined in terms of satisfying a set of 3-bit parity constraints, but this tiny number of bits is reached at the cost of sacrificing full completeness in the verifier: instances where all of these constraints can be satisfied won't happen (the system of linear equations in GF(2) induced by these constraints is over-determined), so if we use these constraints to literally define a problem as in my first paragraph, we will just define the empty set. On the contrary, I'm interested in NP-hard problems.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.