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. 
Lieu178 
OrateurValia Mitsou 
Emailhttps://www.irif.fr/~vmitsou/ 
UrlUniversité Paris Diderot, IRIF 



Aucun document lié à cet événement.

Retour
Retour à l'index