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.
