Nie jesteś zalogowany |
Proof complexity of constraint satisfaction problems
- Prelegent(ci)
- Joanna Ochremiak
- Afiliacja
- Universite Paris Diderot
- Termin
- 12 kwietnia 2017 14:15
- Pokój
- p. 5870
- Seminarium
- Seminarium „Teoria automatów”
In this talk I will define a few "popular" proof systems and argue that constraint satisfaction problems which admit small size refutations in those proof systems are exactly the constraint satisfaction problems which can be solved by local consistency methods.
