Winners of the 2018 Alonzo Church Award

By   11 April 2018

The 2018 Alonzo Church Award for Outstanding Contributions to Logic and Computation is given jointly to Tomás Feder and Moshe Y. Vardi for their fundamental contributions to the computational complexity of constraint-satisfaction problems.

Their contributions appeared in two papers:

Tomas Feder and Moshe Y. Vardi. Monotone Monadic SNP and Constraint Satisfaction. STOC 1993, 612-622.

Tomas Feder and Moshe Y. Vardi. The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory. SIAM J. Comput. 28(1), 57–104 (1998).

Description of the Contribution

The Feder-Vardi project aimed at finding a large subclass of NP that exhibits a dichotomy (all problems are either in PTIME or NP-complete). The approach is to find this subclass via syntactic
prescriptions. The paper identified a class of problems specified by “monotone monadic SNP without inequality”, which may exhibit this dichotomy. Feder and Vardi justified placing all three restrictions by showing, using Ladner’s theorem, that classes obtained by using only two of the above three restrictions do not show this dichotomy. They then explored the structure of this class. They show that all problems in this class reduce to the seemingly simpler class CSP – Constraint Satisfaction Problems. They divided CSP into subclasses and tried to unify the collection of all known polytime algorithms for CSP problems and extract properties that make CSP problems NP-hard. They conjectured that the class CSP (and therefore, also MMSNP) also satisfy the dichotomy property. This became known as the Feder-Vardi Dichotomy Conjecture. The Dichotomy Conjecture stimulated an extensive research program, which culminated in 2017 in two independent proofs, by A. Bulatov and by D. Zhuk, of its correctness.

Details of the Contribution

Descriptive complexity is a branch of computational-complexity theory and of finite-model theory that characterizes complexity classes by the type of logic needed to express the languages in them.
For example, PH, the union of all complexity classes in the polynomial hierarchy, is precisely the class of languages expressible by statements of second-order logic. This connection between complexity and the logic of finite structures allows results to be transferred easily from one area to the other, facilitating new proof methods and providing additional evidence that the main complexity classes are somehow “natural” and not tied to the specific abstract machines used to define them. The first main result of descriptive complexity was Fagin’s Theorem, shown by Ronald Fagin in 1974. It established that NP is precisely the set of languages expressible by sentences of existential second-order logic (ESO); that is, second-order logic excluding universal quantification
over relations, functions, and subsets.

By Ladner’s Theorem, assuming P ≠ NP, the complexity class NP does not have the Dichotomy Property, that is, there are problems in NP that are neither in PTIME nor NP-complete. Feder and Vardi looked for an expressive syntactical fragment of ESO that would be more “well-behaved” than ESO by satisfying the Dichotomy Property. They argued that the class MMSNP, monotone monadic SNP without inequality, which is expressive enough to express many problems, may be such a class; furthermore, it is syntactically maximal. (SNP is a syntactical fragment of ESO, in which the first-order quantifiers must be universal.) Feder and Vardi went on to show that MMSNP reduces to CSP – the class of Constraint Satisfaction Problems. Constraint satisfaction is a subject of central significance in computer science, since a very large number of combinatorial problems, starting from Boolean Satisfiability and Graph Coloring, can be phrased as constraint satisfaction problems.

Feder and Vardi pointed out that constraint satisfaction can be viewed also as the Homomorphism Problem, where we have to decide if there is a homomorphism from a finite source structure A to a finite target structure B. It is easy to see that in its full generality the Homomorphism Problem is NP-complete, but fixing the structure B yields a collection of homomorphism problems, one for each fixed target structure B; this collection of homomorphism problems is the class CSP. Feder and Vardi pointed out that for two special settings of CSP, one in which the structure B has at most two elements and one in which the structures (both source and target) are restricted to be undirected graphs, the Dichotomy Property was already known. They generalized this observation and conjectured that CSP (and consequently, also MMSNP) also satisfy the Dichotomy Property. This became known as the Feder-Vardi Dichotomy Conjecture.

Feder and Vardi then analyzed known polytime algorithms for constraint satisfaction and showed that they have either a logical flavor (constraint propagation) or an algebraic flavor (Gaussian Elimination). They formalized these algorithms in terms of Datalog and Group Theory, respectively, and conjectured that all polytime algorithms for CSP problems can be explained in these terms.

The Feder-Vardi paper launched an extensive research program; the two papers together have close to 1,000 citations on Google Scholar. One direction investigated putting restrictions on the source structure A rather than the target structure B in the homomorphism problem. This is motivated, for example, by the desire to identify classes of conjunctive database queries that have a tractable evaluation problem. In fact, a 1998 paper by Kolaitis and Vardi on “Conjunctive-query containment and constraint satisfaction” has won the 2008 ACM PODS Alberto O. Mendelzon Test-of-Time-Award. Other investigation focused on a richer complexity-theoretic perspective, for example, considering not only the decision problem of CSP but also the counting problem for CSP. Yet another line of research allowed the target structure B to be infinite.

But the “holy grail” of the follow-up research program was the Dichotomy Conjecture. It was quickly realized by other researchers that the algebraic framework proposed by Feder and Vardi – based on group theory – was too narrow, and should be replaced by the more general framework of universal algebra, an algebraic branch of model theory. This algebraic formulation, using the concept of polymorphism (which was suggested informally in the Feder-Vardi paper) turned out to be able to express both constraint propagation and Gaussian Elimination. The universal-algebraic formulation led to a very fruitful interaction between complexity theory and universal algebra. This interaction finally led last year to a positive resolution of the Dichotomy Conjecture, independently by A. Bulatov and D. Zhuk (both presented in FOCS’17), a result described in December 2017 by Lance Fortnow in his popular Computational Complexity blog as “The Theorem of the Year”. But even though the conjecture has been resolved, the research program launched by Feder and Vardi is still continuing vigorously (the paper was cited about 100 times in 2017 alone), due to the many extensions to the original setting that have been proposed over the years.