The class P of polynomial-time computable decision problems is the most important complexity class for the study of efficient computation. Unfortunately, our understanding of the class P is quite limited. The P-NP millenium problem is wide open; but even if we assume that P is different from NP, the class P remains full of mysteries. There are a handful known powerful polynomial-time algorithms and plenty of reduction techniques between polynomial-time problems. It appears that a better understanding of the class P requires both algorithmic insights and a systematic theory of reductions between computational problems. 

Within the microcosm of finite-domain constraint satisfaction problems (CSPs), the recent resolution of the Feder-Vardi dichotomy conjecture by Bulatov and by Zhuk provides a quite satisfactory picture of the class P. On the one side, there is a powerful theory for obtaining polynomial-time (or even logspace) reductions, and the cases which are NP-hard can be proven so by applying a very specific kind of reduction from the 3-SAT problem. On the other side, the cases that are not NP-hard can be solved in polynomial time by Bulatov’s and by Zhuk’s algorithm. 

The dichotomy has been extended to finite-domain valued CSPs (VCSPs), which is a rich class of computational problems that allows to model discrete optimisation problems: every such problem is either in P or NP-hard. This remarkable result does not only rely on the Bulatov-Zhuk theorem, but also on another key protagonist for understanding the class P, namely linear programming. The key ingredient to the great progress in this field is the so-called universal algebraic approach which links questions about constraint satisfaction to questions that are of central interest in universal algebra. 

An important further generalisation of the finite-domain CSP microcosm is the setting of promise CSPs (PCSPs) which allows to model problems from complexity of approximation.  It turns out that the universal-algebraic approach can also be applied in this setting, linking the topic with the PCP theorem and the unique games conjecture. 

Dropping the finite-domain assumption (so that linear programming itself can be viewed as a valued CSP) is the key for further substantial generalisation of the scope where we might hope for complete understanding of the complexity class P. 

Progress in these directions would significantly advance our understanding of the complexity class P and the nature of efficient computation.