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.