TR09-059 Authors: GĂˇbor Kun, Mario Szegedy

Publication: 25th July 2009 12:12

Downloads: 2558

Keywords:

The well known dichotomy conjecture of Feder and

Vardi states that for every ﬁnite 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 iﬀ 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 deﬁnitions that rely on asymptotic properties

of term operations.