NEXPTIME-complétude
Par David Monniaux le mercredi, août 3 2011, 10:12 - Théorie - Lien permanent
J'ai un problème d'analyse de programmes qu'il serait trop fastidieux d'expliciter ici ; il s'agit d'une généralisation du problème traité dans mon récent article avec Thomas Gawlitza. Sauf erreur (je n'ai pas mis la preuve au propre) ce problème est dans NEXPTIME. Je soupçonne qu'hélas ce problème est NEXPTIME-complet. Je m'y connais fort peu en NEXPTIME (d'habitude, je ne regarde que des problèmes dans les premiers degrés de la hiérarchie polynomiale, ou PSPACE-complets) ; connaîtriez-vous des lectures à me conseiller ?
Commentaires
Le problème NEXPTIME-dur que je trouve le plus pratique pour construire des réductions est le pavage de couloir sous contraintes (cf. par exemple Section 3.2 de D. S. Johnson. A catalog of complexity classes. In Handbook of Theoretical Computer Science. MIT Press, 1990). On peut toujours partir des machines de Turing, sinon.
@Bubu: Je crois que je vais partir du problème de l'existence de cycles hamiltoniens dans un graphe donné sous forme succincte, c'est-à-dire que la présence ou non d'une arête (i,j) est donnée par un circuit booléen dont les entrées sont les codages binaires de i et j. Ce problème est NEXPTIME-complet (Papadimitriou & Yannakakis, A note on succinct representations of graphs, Information and control, vol 71 num 3, décember 1986, pp. 181—185).
Je précise que j'ai trouvé mention de ce problème... sur Wikipédia. (je vais y rajouter la référence bibliographique.)