You need to know: Algorithm, running time of an algorithm, class P, class NP, NP-complete problems.
Background: Let be a finite set. Let be a set of n variables taking values in . An assignment means that we assign to each variable the value . A relation R is a subset of , where is a positive integer. A constraint (corresponding to R) is a k-element subset of . We say that assignment satisfies the constraint if . Let be a finite set of relations. A constraint satisfaction problem is: given , , finite set of relations such that each , and a finite set of constraints (each constraint corresponds to some relation ), is there an assignment that satisfies all the constraints?
The Theorem: On 8th March 2017, Andrei Bulatov submitted to arxiv a paper in which he proved that, for every fixed , the problem is either solvable in polynomial time or is NP-complete.
Short context: In 1975, Ladner proved that, if , then there are problems in NP which are neither in P not NP-complete. However, the problems constructed in the proof of this theorem are rather artificial. In practise, most “natural” problems are either in P or NP-complete. Formalising this observation, Feder and Vardi in 1993 noticed that a large variety of “natural” problems are the special cases of , and conjectured that in fact every is either in P or NP-complete. This conjecture became known as the Dichotomy conjecture. The Theorem confirms this conjecture. In a well defined sense, the class of problems is the largest subclass of NP in which such a dichotomy holds.
Links: Free arxiv version of the original paper is here.
Theorems of the 21st century 