Et si SAT était vraiment difficile? Quelques conséquences des hypothèses ETH et SETH
Appears in collection : ALEA Days 2023 / Journées ALEA 2023
Si l'hypothèse P $\neq$ NP a pour conséquence que les problèmes NP-difficiles ne sont pas résolubles en temps polynomial, l'obtention de résultats négatifs plus précis nécessite le recours à des hypothèses plus fortes. Dans cet exposé, nous présenterons certains résultats négatifs (bornes inférieures de complexité) obtenus à partir des hypothèses ETH (exponential time hypothesis) et SETH (strong exponential time hypothesis). Il y sera question de SAT, de graphes, de complexité (classique et parfois paramétrée), de problèmes difficiles mais aussi de problèmes polynomiaux.
