Comment pouvons-nous exprimer «

1. Comment exprimer " " comme une formule de premier ordre?$P=PSPACE$
2. Quel niveau de la hiérarchie arithmétique contient cette formule (et quel est le niveau minimum actuellement connu de la hiérarchie qui la contient)?

Pour référence, voir cet article de blog de Lipton .

Premièrement, je veux adresser les commentaires à la question, où il a été suggéré que "faux" exprime parce que la déclaration est fausse. Bien que cela puisse être une bonne blague, il est en fait très nocif de penser de cette façon. Lorsque nous demandons comment exprimer une certaine phrase dans un certain système formel, nous ne parlons pas de valeurs de vérité. Si nous l'étions, alors quand quelqu'un a demandé "Comment puis-je écrire le fait qu'il existe une infinité de nombres premiers?" nous pourrions répondre "3 + 3 = 6", mais cela ne fera clairement pas l'affaire. Pour la même raison, "false" n'est pas une réponse valide à "comment écrire ?". Je pense que Frege et Russell ont fait de gros efforts pour nous enseigner cette leçon. Ok, maintenant à la réponse.P = P S P A C $P = PSPACE$$P = PSPACE$

Permettez - moi de montrer comment exprimer , l'autre direction est similaire, et vous pouvez les mettre ensemble dans une conjonction pour obtenir . Dans tous les cas, à vos fins , il peut être suffisant pour exprimer juste , en fonction de ce que vous faites.P S P A C E = P P S P A C E ⊆ $PSPACE \subseteq P$$PSPACE = P$$PSPACE \subseteq P$

En utilisant des techniques similaires à celles de la construction du prédicat$T$ de Kleene , nous pouvons construire une formule bornée accept_ (qui réside donc dans ) en disant "quand nous exécuter la machine encodée par et lié son utilisation d'espace à , la machine accepte l'entrée . " Iciest la longueur de . Une façon informelle de voir que de telles formules existent est la suivante: étant donné , et nous pouvons calculer une limite récursive primitive sur le temps et l'espace dont nous aurons besoin (c'est-à-dire, tout au plusΣ 0 0 = Π 0 0 k | n | m n | n | n k m n | n | m 2 | n | $accept_{space}(k, m, n)$$\Sigma^0_0 = \Pi^0_0$$k$$|n|^m$$n$$|n|$$n$$k$$m$$n$$|n|^m$ espace et au plus temps). Nous recherchons ensuite simplement toutes les traces d'exécution possibles qui se trouvent dans les limites calculées - une telle recherche est plutôt inefficace, mais elle est récursive primitive et nous pouvons donc l'exprimer sous la forme d'une formule bornée.$2^{|n|^m}$

Il existe une formule similaire dans laquelle le temps d'exécution est lié par .| n | $accept_{time}(k, m, n)$$|n|^m$

Considérons maintenant la formule: Il dit que pour chaque machine qui utilise au maximum l'espace il y a une machine qui utilise au plus le temps telle sorte que les deux machines acceptent exactement les mêmes . En d' autres termes, la formule dit . Cette formule est .k | n | m k

Nous pouvons améliorer cela si nous sommes prêts à exprimer au lieu de la phrase « est polynomial », qui devrait être assez bon pour la plupart des applications, comme TQBF est PSPACE complet et donc qu'il soit en polynomial équivaut à . Soit (le code de) une machine qui reconnaît TQBF dans l'espace . Alors " " peut être exprimé comme Cette formule est juste Σ 0 2 . Si j'étais un théoricien de la complexité, je saurais s'il est possible de faire encore mieux (mais j'en doute).P S P A C E ⊆ P k 0 | n | m 0 T Q B F ∈ P ∃ k ′ , m ′ . ∀ n . a c c e p t s p a c e ( k 0 , m 0 , n ) ⇔ a c c e $TQBF$$PSPACE \subseteq P$$k_0$$|n|^{m_0}$$TQBF \in P$

$P=\mathit{PSPACE}$$\Sigma^0_2$$\Pi^0_2$$A$$P^A=\mathit{PSPACE}^A$$\Sigma^0_2$$A$$\Pi^0_2$$P=\mathit{NP}$$\mathit{PSPACE}$$\Sigma^0_2$

EDIT: La preuve topologique donnée dans le commentaire lié est courte, mais elle peut sembler délicate. Voici un argument de forçage direct.

$P^A\ne\mathit{PSPACE}^A$$\Pi^0_2$$\phi(A)=\forall x\,\exists y\,\theta(A,x,y)$$\theta$$\Delta^0_0$$P^A=\mathit{PSPACE}^A$$\Pi^0_2$$\psi(A)=\forall x\,\exists z\,\eta(A,x,z)$$B$$C$$P^B\ne\mathit{PSPACE}^B$$P^C=\mathit{PSPACE}^C$

$\phi(B)$$y_0$$\theta(B,0,y_0)$$\theta$$\theta(B,0,y_0)$$b_0$$B$$\theta(A,0,y_0)$$A$$b_0$

$C[b_0]$$b_0$$C$$b_0$$P^A$$\mathit{PSPACE}^A$$\psi(C[b_0])$$z_0$$c_0$$C[b_0]$$\eta(A,0,z_0)$$A$$c_0$$c_0$$b_0$

$y_0,y_1,y_2,\dots$$z_0,z_1,z_2,\dots$$b_0\subseteq c_0\subseteq b_1\subseteq c_1\subseteq b_2\subseteq\cdots$

1. $\theta(A,n,y_n)$$A$$b_n$

2. $\eta(A,n,z_n)$$A$$c_n$

$A$$b_n$$c_n$$\phi(A)$$\psi(A)$