期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2009
卷号：2009
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 re- formulated this conjecture in terms of the properties of the algebra P ol(Γ), 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 arbi- trarily resilient functions in P ol(Γ). Equivalently, we can express this in the terms of the PCP theory: CSP(Γ) is NP-hard iff all long code tests created from Γ that passes with zero error admits only juntas1. Then, using this characterization and a result of Dinur, Friedgut and Regev, we give an entirely new and transparent proof to the Hell-Neˇsetˇril theorem, which states that for a simple, con- nected 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'. The complexity of this class is unknown. Several authors conjectured that CSP problems without the ability to count have bounded width, or equivalently, that they can be characterized by existential k-pebble games. The resolution of this conjecture would be a ma jor step towards the resolution of the dichotomy conjecture. We show that CSP problems without the ability to count are exactly the ones with strongly resilient term operations, which might give a handier tool to attack the conjecture than the known algebraic characterizations. Finally, we show that a yet stronger notion of resilience, when the term operation is asymptotically constant, allows us to char- acterize the class of width one CSPs. What emerges from our research, is that certain important al- gebraic conditions that are usually expressed via identities have equivalent analytic definitions that rely on asymptotic properties of term operations.
