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.”