ALEA Days / Journées ALEA

Collection ALEA Days / Journées ALEA

Organizer(s) Elvey Price, Andrew ; Lecouvey, Cédric ; Mailler, Cécile ; Raschel, Kilian
Date(s) 13/03/2023 - 15/03/2023
linked URL https://conferences.cirm-math.fr/2887.html
00:00:00 / 00:00:00
32 34

Et si SAT était vraiment difficile? Quelques conséquences des hypothèses ETH et SETH

By Bruno Escoffier

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.

Information about the video

Citation data

  • DOI 10.24350/CIRM.V.20018103
  • Cite this video Escoffier, Bruno (14/03/2023). Et si SAT était vraiment difficile? Quelques conséquences des hypothèses ETH et SETH. CIRM. Audiovisual resource. DOI: 10.24350/CIRM.V.20018103
  • URL https://dx.doi.org/10.24350/CIRM.V.20018103

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow




Register

  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
    community
  • Get notification updates
    for your favorite subjects
Give feedback