Quelle est la complexité de calcul de la logique propositionnelle intuitionniste?

Question

Considérez le problème de décision: compte tenu des formules de logique propositionnelle $ phi_1, ldots, phi_n, psi $, déterminer si $ phi_1, ldots, phi_n vdash psi $ intuitionniste. Ce problème est bien connu pour être décidable, par exemple en utilisant un algorithme dérivé du Calcul séquentiel LJT *. Je me demandais si la complexité de calcul de ce problème est connue.

Trivialement, la complexité est équivalente au polynôme à la complexité du problème de tautologie intuitionniste: $ phi_1, ldots, phi_n vdash psi $ si et seulement si $ phi_1 wedge ldots wedge phi_n rightarrow psi $ est une tautologie; et inversement, $ phi $ est une tautologie si et seulement si $ vdash phi $. Certes, le problème est le co-np-hard: en corollaire de l'intégration à double négation, une formule $ phi $ est classiquement satisfait si et seulement si $ lnot phi $ n'est pas une tautologie de la logique intuitionniste.

D'un autre côté, si je ne me trompe pas, le problème est dans PSPACE: la seule règle de LJT * qui pourrait éventuellement augmenter la durée totale d'un contexte de preuve est dans le premier sous-ogin de $ ( alpha, beta rightarrow gamma, gamma vdash beta) wedge ( gamma, gamma vdash delta) implique ( alpha droite beta) droite gamma, gamma vdash delta $. Mais dans ce cas, la deuxième copie de $ bêta $ devrait encore être au plus égal à la longueur d'une formule dans le contexte d'origine.

(Aussi, depuis le Treillis Rieger-Nishimura, l'algèbre HEYting gratuite sur un générateur, a une description calculable simple, le cas particulier de ce problème limité aux problèmes avec un seul atome serait dans P. ce serait une restriction grave, cependant.)

Au-delà de cela, dans une recherche rapide sur Google, je n'ai trouvé aucun résultat directement sur ce problème, juste quelques articles où les résumés semblaient indiquer qu'ils envisageaient des fragments de logique propositionnelle. Je ne trouve pas non plus de preuve par moi-même qui affinerait le statut. (Par exemple, pour tout ce que je sais, il peut être possible que chaque fois que la séquente ne soit pas intuitionniste valide, il existe un modèle Kripke de taille polynomiale qui le démontre - auquel cas le problème serait Co-NP-complete. Ou plus généralement généralement , une algèbre Heyting avec une "description" de la taille du polynôme suffirait. Il est plus difficile pour moi d'imaginer un moyen de réduire un problème tel que QBF à une instance de ce problème pour prouver que c'est PSPACE-COMPLET, bien que je ne puisse pas non plus entièrement exclure la possibilité.)