# Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | future lectures)

On 13.12.2007 at 12:20 in S5, there is the following noon lecture:

# Weak near-unanimity and constraint satisfaction problems

## Miklos Maroti

## University Szeged

## Abstract

We will discuss how weak near-unanimity operations can be used to prove the NP-completeness of constraint satisfaction problems. As an application, we will outline the proof of dichotomy for a class of graphs, called special triads.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | future lectures)

Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010