![School of Mathematics Event](/sites/default/files/styles/two_column_medium/public/2019-09/sm_default.jpg?itok=gMvWynkh)
Computer Science/Discrete Mathematics Seminar II
Dichotomy Conjecture for Constraint Satisfaction Problems
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.
Date & Time
November 11, 2008 | 10:30am – 12:30pm
Location
S-101Speakers
Affiliation
Renyi Institute and Member, School of Mathematics