|
Énumération Algorithmique III. Difficultés de l’énumération et réductions polynomiales| title | Énumération Algorithmique III. Difficultés de l’énumération et réductions polynomiales |
|---|
| start_date | 2023/10/09 |
|---|
| schedule | 10h |
|---|
| online | no |
|---|
| location_info | lieu non précisé |
|---|
| details | Séminaire ACRO |
|---|
| summary | Cet exposé est le troisième d’une série d’exposés sur le thème de l’énumération algorithmique où seront présentés différentes techniques, résultats et problèmes ouverts dans ce domaine relativement récent. Dans cet épisode, on s’intéressera aux réductions polynomiales entre problèmes d’énumération, et à la preuve de leur difficulté qui se traduit bien souvent par « il n’existe pas d’algorithme total-polynomial pour Π à moins que P = NP » et qui de fait exclut la possibilité d’algorithmes à délai polynomial ou incrémental polynomial. On s’intéressera en particulier aux problèmes d’énumération des indépendants maximaux donnés par un oracle, à l’énumération des modèles maximaux d’une formule de Horn, et à la place importante que s’est faite la dualisation des fonctions monotones Booléennes en énumération. |
|---|
| responsibles | NC |
|---|
Workflow history| from state (1) | to state | comment | date |
|---|
| submitted | published | | 2023/10/09 13:42 UTC |
| |
|