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

Date 2018-03-27  11:00-12:00
TitreLimitations of treewidth for problems beyond NP. 
Résumé***Joint seminar with Graphes et Optimisation*** In this seminar, we will take a closer look at the parameterized complexity of existsforallSAT, the prototypical complete problem of the class $Sigma^p_2$, the second level of the polynomial hierarchy. We will provide tight fine-grained bounds on the complexity of this problem with respect to the most important structural graph parameters. Specifically we will show that existsforallSAT cannot be solved in time $2^{2^{o(tw)}}$ under the Exponential Time Hypothesis. More strongly, we establish the same bound with respect to the formula’s primal vertex cover, a much more restrictive measure. Our reduction is a 'textbook' reduction that could be used in order to provide similar lower bounds for problems in the second level of the polynomial hierarchy. 
OrateurValia Mitsou 
UrlUniversité Paris Diderot, IRIF 

Aucun document lié à cet événement.

Retour à l'index