Existe-t-il une solution en temps polynomiale pour repli ?

tout est dans le titre :D

J'ai pas réussi à trouvé d'équivalence avec un problème NP-Complet existant du coup, je voulais savoir si il existe une solution astucieuse en temps polynomial ou pas pour ce problème ?

Si je m'en tiens à ce que j'ai entendu, le fait que ca conserve l'ordre fait que e problème n'est pas NP-complet mais il l'aurait été si ca ne conservait pas l'ordre.

C'est ce que je pensais aussi concernant la NP-completude. Du coup, t'utilises quelle stratégie pour ne pas avoir à tester toutes les possibilités ?

Effectivement, sans cette propriété, c'est NP-complet (merci Wikipedia) :

> [...] as Eppstein also shows, the problem of finding the shortest synchronizing word is NP-complete. However, for a special class of automata in which all state transitions preserve the cyclic order of the states, he describes a different algorithm with time O(k * n\^2) that always finds the shortest synchronizing word [...].

Donc oui, c'est possible en temps polynomial.

Il ne fallait considérer que les intervalles et non les ensembles de positions (il y a O(n\^2) intervalles et O(2\^n) ensembles.)
Ensuite, il fallait juste faire attention quand les deux bornes de l'intervalle amenaient sur la même position car il était possible qu'une autre position dans le même intervalle amène ailleurs (dans quel cas il suffisait d'ignorer la transition.)

Le nom « canonique » de ce problème est « mot synchronisant minimum dans un automate monotone », on va mettre une correction en ligne.