|
Evènement pour le groupe Séminaire Méthodes Formelles
Date | 2018-03-27 11:00-12:00 |
Titre | Limitations 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. |
Lieu | 178 |
Orateur | Valia Mitsou |
Email | https://www.irif.fr/~vmitsou/ |
Url | Université Paris Diderot, IRIF |
Aucun document lié à cet événement. RetourRetour à l'index
| |