A new line of attack on the dichotomy conjecture

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(Γ). 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 to characterize CSP problems that 'do not have the ability to count.' Very recently this class has been shown to be equivalent with the the class of bounded width problems, i.e. the class of CSPs that be described by existential k-pebble games. What emerges from our research, is that certain important algebraic conditions that are usually expressed via identities have equivalent definitions that rely on asymptotic properties of term operations. Our new notions have a potential to show hardness of CSPs (as demonstrated on the Hell-Nesetril theorem), or to prove their tractability.

REFERENCES

• 1: . Barto, M. Kozik, T. Niven, CSP dichotomy holds for digraphs with no sink and source, SIAM J. on Computing,accepted, 2008.
• 2: . Barto, M. Kozik, Constraint Satisfaction Problems of bounded width, manuscript.
• 3: Pawel Idziak , Petar Markovic , Ralph McKenzie , Matthew Valeriote , Ross Willard, Tractability and learnability arising from algebras with few subpowers, Proceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science, p.213-224, July 10-14, 2007 [doi>10.1109/LICS.2007.50]
• 4: Andrei A. Bulatov, A dichotomy theorem for constraint satisfaction problems on a 3-element set, Journal of the ACM (JACM), v.53 n.1, p.66-120, January 2006 [doi>10.1145/1120582.1120584]
• 5: Andrei A. Bulatov, Tractable conservative Constraint Satisfaction Problems, Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science, p.321, June 22-25, 2003
• 6: Andrei Bulatov , Víctor Dalmau, A Simple Algorithm for Mal'tsev Constraints, SIAM Journal on Computing, v.36 n.1, p.16-27, 2006 [doi>10.1137/050628957]
• 7: Andrei A. Bulatov , Víctor Dalmau, Towards a dichotomy theorem for the counting constraint satisfaction problem, Information and Computation, v.205 n.5, p.651-678, May, 2007 [doi>10.1016/j.ic.2006.09.005]
• 8: Andrei A. Bulatov , Andrei A. Krokhin , Peter Jeavons, Constraint Satisfaction Problems and Finite Algebras, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.272-282, July 09-15, 2000
• 9: Peter Jeavons , David Cohen , Martin C. Cooper, Constraints, consistency and closure, Artificial Intelligence, v.101 n.1-2, p.251-265, May 1998 [doi>10.1016/S0004-3702(98)00022-8]
• 10: Peter Jeavons , David Cohen , Marc Gyssens, Closure properties of constraints, Journal of the ACM (JACM), v.44 n.4, p.527-548, July 1997 [doi>10.1145/263867.263489]
• 11: . Dalmau, Generalized majority-minority operations are tractable, LICS05.
• 12: Phokion G. Kolaitis , Moshe Y. Vardi, Conjunctive-query containment and constraint satisfaction, Journal of Computer and System Sciences, v.61 n.2, p.302-332, Oct. 2000 [doi>10.1006/jcss.2000.1713]
• 13: Víctor Dalmau , Justin Pearson, Closure Functions and Width 1 Problems, Proceedings of the 5th International Conference on Principles and Practice of Constraint Programming, p.159-173, October 11-14, 1999
• 14: Irit Dinur, The PCP theorem by gap amplification, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132553]
• 15: rit Dinur, Ehud Friedgut, Oded Regev, Independent Sets in Graph Powers are Almost Contained in Juntas, Geometric and Functional Analysis, accepted.
• 16: Tomás Feder , Moshe Y. Vardi, The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory, SIAM Journal on Computing, v.28 n.1, p.57-104, Feb. 1999 [doi>10.1137/S0097539794266766]
• 17: Jan Foniok , Jaroslav Nešetřil , Claude Tardif, Generalised dualities and maximal finite antichains in the homomorphism order of relational structures, European Journal of Combinatorics, v.29 n.4, p.881-899, May, 2008 [doi>10.1016/j.ejc.2007.11.017]
• 18: Pavol Hell , Jaroslav Nešetřil, On the complexity of H-coloring, Journal of Combinatorial Theory Series B, v.48 n.1, p.92-110, Feb. 1990 [doi>10.1016/0095-8956(90)90132-J]
• 19: . Hell, J. Nesetril, Colouring, Constraint Satisfaction and Complexity, manuscript, 2008. http://iti.mff.cuni.cz/series/files/iti413.eps
• 20: . Hell, J. Nesetril, X. Zhu, Duality and polynomial testing of tree homomorphisms, Transactions of the American Mathematical Society, 348(4):1281--1297, 1996.
• 21: . Kun, Constraints, MMSNP and expanderrelational structures, Combinatorica, submitted.
• 22: Gábor Kun , Jaroslav Nešetřil, Forbidden lifts (NP and CSP for combinatorialists), European Journal of Combinatorics, v.29 n.4, p.930-945, May, 2008 [doi>10.1016/j.ejc.2007.11.027]
• 23: Richard E. Ladner, On the Structure of Polynomial Time Reducibility, Journal of the ACM (JACM), v.22 n.1, p.155-171, Jan. 1975 [doi>10.1145/321864.321877]
• 24: . Larose, L. Zádori, M. Valeriote, Omitting types, bounded width and the ability to count, manuscript, 2008.
• 25: . McKenzie, M. Maróti: Existence theorems for weakly symmetric operations, Algebra Universalis, to appear.
• 26: . Nesetril, M. Siggers, L. Zádori:phA Combinatorial constraint satisfaction problem dichotomy classification conjecture, manuscript, 2007.
• 27: Jaroslav Nešetřil , Xuding Zhu, On bounded treewidth duality of graphs, Journal of Graph Theory, v.23 n.2, p.151-162, Oct. 1996 [doi>10.1002/(SICI)1097-0118(199610)23:2<151::AID-JGT6>3.3.CO;2-K]
• 28: Y. Rabinovich , A. Sinclair , A. Wigderson, Quadratic dynamical systems, Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, p.304-313, October 24-27, 1992 [doi>10.1109/SFCS.1992.267761]
• 29: Thomas J. Schaefer, The complexity of satisfiability problems, Proceedings of the tenth annual ACM symposium on Theory of computing, p.216-226, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804350]
• 30: s. Szabó, L. Zádori, Idempotent totally symmetric operations on finite posets, Order 18,39--47, 2001 .

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms

Keywords:
NP, computational complexity, constraint satisfaction problems, dichotomy, fourier analysis, term operations