Le modèle vérifie-t-il PSPACE-HARD * dans la taille de la formule *?

Question

Sistla / Clarke s'est avéré [SC82] que le problème de vérification du modèle LTL est PSPACE-Complete. Parfois, les gens écrivent que ce problème est "PSPACE-DUR dans $ | phi | $" (par exemple [LP85]). Qu'est-ce que cela signifie formellement?

Comment prouver qu'un problème de décision qui a plusieurs paramètres (ici, $ phi $ et le système) est-ce que PSPACE est dur dans l'un des paramètres? Je suppose que nous aurions besoin de réduire en poly-temps un problème de complets PSPACE à notre problème avec le paramètre sans intérêt fixe, tandis que le paramètre intéressant peut varier.

Mais la preuve originale de Sistla / Clarke [lemme 4.4, SC82] ne fait pas la chose ci-dessus! Dans leur preuve, les deux paramètres de l'instance de problème de vérification du modèle LTL résultant dépendent de $ n $, où $ n $ est le ruban TM lié. Existe-t-il une preuve qui corrige l'un des paramètres?