00:00:00 / 00:00:00

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

By Bruno Escoffier

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.

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
Loading…
Loading the web debug toolbar…
Attempt #