A new line of attack on the dichotomy conjecture

Kun, Gábor and Szegedy, Mario (2016) A new line of attack on the dichotomy conjecture. EUROPEAN JOURNAL OF COMBINATORICS, 52. pp. 338-367. ISSN 0195-6698

	Text 1_s2.0_S0195669815001778_main_u.pdf - Published Version Restricted to Registered users only Download (731kB) | Request a copy
Preview	Text TR09_059_u.pdf - Submitted Version Download (1MB) | Preview

Abstract

The well known dichotomy conjecture of Feder and Vardi states that for every finite family Γ of constraints CSP. (Γ) is either polynomially solvable or NP-hard. Bulatov and Jeavons reformulated this conjecture in terms of the properties of the algebra Pol(Γ), where the latter is the collection of those n-ary operations (n= 1, 2, . . .) that keep all constraints in Γ invariant. We show that the algebraic condition boils down to whether there are arbitrarily resilient functions in Pol(Γ). Equivalently, we can express this in terms of the PCP theory: CSP. (Γ) is NP-hard iff every long code test created from Γ that passes with zero error admits only juntas. Then, using this characterization and a result of Dinur, Friedgut and Regev, we give an entirely new and transparent proof to the Hell-Nešetřil 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 bounded width, or equivalently, that they can be characterized by existential k-pebble games: Barto and Kozik already proved this conjecture using a variant of our characterization. This is considered a major step towards the resolution of the dichotomy conjecture. Finally, we show that a yet stronger notion of resilience, when the term operation is asymptotically constant, holds for the class of width one CSPs. What emerges from our research, is that certain important algebraic conditions that are usually expressed via identities have equivalent analytic definitions that rely on asymptotic properties of term operations. © 2015 Elsevier Ltd.

Actions (login required)

Edit Item