Je considère une extension du problème discuté dans un de mes articles récents, extension qu'il serait assez fastidieux de décrire ici. On voit facilement que le problème de décision associé est dans NEXPTIME et est PSPACE-dur.

Mon problème serait-il PSPACE-complet ? Je ne vois pas de raison pour laquelle le problème serait dans PSPACE, pas plus que de raison pour laquelle il serait dans EXPTIME.

Mon problème serait-il NEXPTIME-complet ? Cela fait un peu plus d'une journée que j'essaye (pas à temps plein) de trouver une réduction d'un problème de graphe succinct NEXPTIME-complet (par exemple le cycle hamiltonien), sans succès.

C'est là je pense une magnifique illustration de la différence entre l'enseignement et la recherche scientifique : quand on donne un problème dans un devoir ou un examen, on connaît la réponse ainsi qu'une démonstration de taille raisonnable (et au besoin on fractionne le problème d'origine). Là, je ne sais pas ce que je dois essayer de montrer.