All reports by Author Gábor Kun:

__
TR09-059
| 2nd July 2009
__

Gábor Kun, Mario Szegedy#### A NEW LINE OF ATTACK ON THE DICHOTOMY CONJECTURE

Gábor Kun, Mario Szegedy

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 ...
more >>>