Développement : Séparation par automate NP-complet

Détails/Enoncé :

Input : k entier et S,T deux langages finis.
Output : Existe t'il un automate A à k états qui sépare S et T.
Ce problème est NP-complet.

Recasages pour l'année 2024 :

  • Pas de recasages pour cette année.

Versions :