Libor Barto

# Baby PCP theorem and reductions between Promise CSPs

The Promise CSP over a pair ($$A,B$$) of similar structures, written PCSP($$A,B$$), is the problem to distinguish, given a similar structure X, between the cases that $$X$$ has a homomorphism to $$A$$ and $$X$$ does not have a homomorphism to $$B.$$ For example, if $$A$$ is the clique on k vertices and $$B$$ is the clique on $$l$$ vertices ($$k < l$$), then PCSP($$A,B$$) is the problem of distinguishing $$k$$-colorable graphs from graphs that are not $$l$$-colorable.

There is a general criterion due to Bulín, Krokhin, and Opršal (BKO) sufficient to prove that PCSP($$A,B$$) can be reduced to PCSP($$C,D$$). In fact, this criterion is now known (as follows from the CSP dichotomy result of Bulatov and Zhuk) to be a perfect tool for proving NP-hardness of “normal” CSPs in the following sense: If $$C = D$$ and PCSP($$C,D$$) is not in P, then the BKO criterion applies to every ($$A,B$$) and we get a reduction from PCSP($$A,B$$) to PCSP($$C,D$$).

However, for distinct $$C$$ and $$D$$, the criterion is no longer perfect and different arguments are sometimes needed to prove NP-hardness of PCSP($$C,D$$). A general NP-hardness criterion was recently isolated in a work of Brandts, Wrochna, and Živný (BWŽ). The criterion is quite powerful and covers a lot of NP-hardness results. However, it lacks the simplicity and beauty of BKO:

1. The NP-completeness is proved by reducing from a gap version of the Label Cover problem which is, strictly speaking, not a PCSP. So BKW do not give us a general way to reduce one PCSP to another.

2. Proving NP-completeness of the required gap version of the Label Cover problem needs the PCP theorem and the Parallel Repetition theorem, quite complicated results.

In a joint work with Marcin Kozik we eliminated these two flies in the ointment by giving a general sufficient condition for reducing PCSP($$A,B$$) to PCSP($$C,D$$) which covers BWŽ and the proof is quite simple. This also gives us a simple proof of NP-hardness of a (weaker) gap version of the Label Cover problem, which might be called a “Baby PCP theorem.”