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 4 |

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.