A new line of attack on the dichotomy conjecture

作者：Kun Gabor^*; Szegedy Mario

来源：European Journal of Combinatorics, 2016, 52: 338-367.

DOI：10.1016/j.ejc.2015.07.011

The well known dichotomy conjecture of Feder and Vardi states that for every finite family Gamma of constraints csp(Gamma) is either polynomially solvable or NP-hard. Bulatov and Jeavons reformulated this conjecture in terms of the properties of the algebra Pol(Gamma), where the latter is the collection of those n-ary operations (n = 1, 2,...) that keep all constraints in Gamma invariant. We show that the algebraic condition boils down to whether there are arbitrarily resilient functions in Pol(Gamma). Equivalently, we can express this in terms of the PCP theory: CSP(Gamma) is NP-hard iff every long code test created from Gamma that passes with zero error admits only juntas.(3) Then, using this characterization and a result of Dinur, Friedgut and Regev, we give an entirely new and transparent proof to the Hell Nesetril theorem, which states that for a simple, connected and undirected graph H, the problem CSP(H) is NP-hard if and only if H is non-bipartite.
We also introduce another notion of resilience (we call it strong resilience), and we use it in the investigation of CSP problems that 'do not have the ability to count'. We show that CSP problems without the ability to count are exactly the ones with strongly resilient term operations. This gave already a handier tool to attack the conjecture that CSP problems without the ability to count have

• 出版日期2016-2
• 单位rutgers