Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Limitations of treewidth for problems beyond NP.
du 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