Evènement pour le groupe Séminaire Méthodes Formelles

Date 2017-10-03  11:00-12:00
TitreProof complexity of constraint satisfaction problems 
RésuméMany natural computational problems, such as satisfiability and systems of equations, can be expressed in a unified way as constraint satisfaction problems (CSPs). In this talk I will show that the usual reductions preserving the complexity of the constraint satisfaction problem preserve also its proof complexity. As an application, I will present two gap theorems, which say that CSPs that admit small size refutations in some classical proof systems are exactly the constraint satisfaction problems which can be solved by Datalog. This is joint work with Albert Atserias. 
OrateurJoanna Ochremiak 

Aucun document lié à cet événement.

Retour à l'index