The 2018 Alonzo Church AwardThe 2018 Alonzo Church Award for Outstanding Contributions to Logic and Computation is given jointly to Tomas Feder and Moshe Y. Vardi for fundamental contributions to the computational complexity of constraint-satisfaction problems. Their contributions appeared in two papers: 1. Tomas Feder, Moshe Y. Vardi: Monotone Monadic SNP and Constraint Satisfaction. STOC 1993, 612-622. 2. Tomas Feder, 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). CONTRIBUTION SUMMARY: 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 Lad- ner’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 exten- sive research program, which culminated in 2017 in two independent proofs, by A. Bulatov and by D. Zhuk, of its correctness. |