Dichotomy Conjecture for Constraint Satisfaction Problems

COMPUTER SCIENCE/DISCRETE MATH II
Topic:Dichotomy Conjecture for Constraint Satisfaction Problems
Speaker:Gabor Kun
Affiliation:Renyi Institute and Member, School of Mathematics
Date:Tuesday, November 11
Time/Room:10:30am - 12:30pm/S-101
The dichotomy conjecture asks if every Constraint Satisfaction Problem is either in P or NP-complete. We will study the basic algorithms and reductions for such problems. We will see many (equivalent) stronger versions of this conjecture actually telling the border between P and NP-completeness.