In the first part of this lecture, we introduce the complexity classes (for polynomial time reductions) P and NP-complete, we give a brief overview of the current status of the millenium problem P vs NP, and review the latest, apparently unsuccessful, attempt at solving it by Vinay Deolalikar. Then we turn to a related problem, the Dichotomy Conjecture for (fixed-template) Constraint Satisfaction Problem, which is the speaker's area of expertise. Constraint Satisfaction Problem (CSP) is a fairly general language useful for expressing a broad range of problems within the class NP. The Dichotomy Conjecture states that for any template, the complexity of the CSP with this template is either in P or NP-complete. This conjecture has been verified in various subcases, and the approaches which have been attempted used the results and ideas of Complexity Theory, Logic, Graph Theory and Universal Algebra (which has been the most fruitful one). We review some of the results and the (weak) connections this problem has with P vs NP.
