<p>Andrej has already explained that $P=\mathit{PSPACE}$ can be written as a $\Sigma^0_2$-sentence. Let me mention that this classification is optimal in the sense that if the statement is equivalent to a $\Pi^0_2$-sentence, then this fact does not relativize. More precisely, the set of oracles $A$ such that $P^A=\mathit{PSPACE}^A$ is definable by a $\Sigma^0_2$-formula with a free second-order variable $A$, but it is not definable by any $\Pi^0_2$-formula. The argument is outlined (for $P=\mathit{NP}$, but it works just the same for $\mathit{PSPACE}$) in the comments at <a href="https://mathoverflow.net/questions/57348">https://mathoverflow.net/questions/57348</a>. (In fact, one can show by an elaboration of the idea that the set is $\Sigma^0_2$-complete in the appropriate sense.)</p>

<p>EDIT: The topological proof given in the linked comment is short, but it may appear tricky. Here is a direct forcing argument.</p>

<p>$P^A\ne\mathit{PSPACE}^A$ can be written as a $\Pi^0_2$-formula of the form $\phi(A)=\forall x\,\exists y\,\theta(A,x,y)$, where $\theta$ is $\Delta^0_0$. Assume for contradiction that $P^A=\mathit{PSPACE}^A$ is also equivalent to a $\Pi^0_2$-formula $\psi(A)=\forall x\,\exists z\,\eta(A,x,z)$. Fix oracles $B$, $C$ such that $P^B\ne\mathit{PSPACE}^B$ and $P^C=\mathit{PSPACE}^C$.</p>

<p>Since $\phi(B)$, there exists $y_0$ such that $\theta(B,0,y_0)$. However, $\theta$ is a bounded formula, hence the evaluation of the truth value of $\theta(B,0,y_0)$ only uses a finite part of the oracle. Thus, there exists a finite part $b_0$ of $B$ such that $\theta(A,0,y_0)$ for every oracle $A$ extending $b_0$.</p>

<p>Let $C[b_0]$ denote the oracle which extends $b_0$, and agrees with $C$ where $b_0$ is undefined. Since $P^A$ and $\mathit{PSPACE}^A$ are unaffected by a finite change in the oracle, we have $\psi(C[b_0])$. By the same argument as above, there exists $z_0$ and a finite part $c_0$ of $C[b_0]$ such that $\eta(A,0,z_0)$ for every $A$ extending $c_0$. We may assume that $c_0$ extends $b_0$.</p>

<p>Continuing in the same fashion, we construct infinite sequences of numbers $y_0,y_1,y_2,\dots$, $z_0,z_1,z_2,\dots$, and finite partial oracles $b_0\subseteq c_0\subseteq b_1\subseteq c_1\subseteq b_2\subseteq\cdots$ such that</p>

<ol>
<li><p>$\theta(A,n,y_n)$ for every oracle $A$ extending $b_n$,</p></li>
<li><p>$\eta(A,n,z_n)$ for every oracle $A$ extending $c_n$.</p></li>
</ol>

<p>Now, let $A$ be an oracle which extends all $b_n$ and $c_n$. Then 1 and 2 imply that $\phi(A)$ and $\psi(A)$ simultaneously hold, which contradicts the assumption that they are complements of each other.</p>

CC BY-SA 3.0
2013-03-01T07:00:19.613Z
Sad that such a nice answer is for a question that's now closed...
arnab
CC BY-SA 3.0
2013-02-25T15:45:45.773Z
2013-02-25T17:15:46.330Z
2017-04-13T12:57:54.777Z
Emil Jeřábek
<p>Firstly, I want to address the comments to the question, where it was suggested that "false" expresses $P = PSPACE$ because the statement <em>is</em> false. While this might be a good joke, it is actually very much harmful to think this way. When we ask how to express a certain sentence in a certain formal system, we are not talking about truth values. If we were, then when someone asked "How do I write down the fact that there are infinitely many primes?" we could answer "3 + 3 = 6", but this clearly will not do. For the same reason "false" is not a valid answer to "how do I write down $P = PSPACE$?". I think Frege and Russell tried hard to teach us that lesson. Ok, now to the answer.</p>

<p>Let me show how to express $PSPACE \subseteq P$, the other direction is similar, and then you can put them together in a conjunction to get $PSPACE = P$. In any case, for your purposes it may be sufficient to express just $PSPACE \subseteq P$, depending on what you are doing.</p>

<p>Using techniques similar to those in the construction of <a href="http://en.wikipedia.org/wiki/Kleene%27s_T_predicate" rel="noreferrer">Kleene's predicate $T$</a>, 
we can construct a bounded quantifer formula $accept_{space}(k, m, n)$ (which thus resides in $\Sigma^0_0 = \Pi^0_0$) saying "when we run the machine encoded by $k$ and bound its space usage to $|n|^m$, the machine accepts the input $n$." Here $|n|$ is the length of $n$. An informal way of seeing that such formulas exists is this: given $k$, $m$, and $n$ we can compute primitive recursive bound on how much time and how much space we are ever going to need (i.e., at most $|n|^m$ space and at most $2^{|n|^m}$ time). We then simply search through all possible execution traces which are within the computed bounds--such a search is rather inefficient, but it is primitive recursive and so we can express it as a bounded formula.</p>

<p>There is a similar formula $accept_{time}(k, m, n)$ in which the running time is bound by $|n|^m$.</p>

<p>Now consider the formula:
$$\forall k, m . \exists k', m' . \forall n .
accept_{space}(k,m,n) \Leftrightarrow accept_{time}(k',m', n).
$$
It says that for every machine $k$ which uses at most space $|n|^m$ there is a machine $k'$ which uses at most time $|n|^{m'}$ such that the two machines accepts exactly the same $n$'s. In other words, the formula says $PSPACE \subseteq P$. This formula is $\Pi^0_3$.</p>

<p>We can improve this if we are willing to express instead the sentence "$TQBF$ is in polytime" , which should be good enough for most applications, as <a href="http://en.wikipedia.org/wiki/PSPACE-complete#TQBF" rel="noreferrer">TQBF</a> is PSPACE complete and so it being in polytime is equivalent to $PSPACE \subseteq P$. Let $k_0$ be (the code of) a machine which recognizes TQBF in space $|n|^{m_0}$. Then "$TQBF \in P$" can be expressed as
$$\exists k', m' . \forall n . accept_{space}(k_0, m_0, n) \Leftrightarrow accept_{time}(k', m', n).$$
This formula is just $\Sigma^0_2$. If I were a complexity theorist I would know if it is possible to do even better (but I doubt it).</p>

CC BY-SA 3.0
2013-02-28T19:31:01.060Z
your first paragraph is almost like a logical, textual form of this: http://xkcd.com/169/
Vijay D
CC BY-SA 3.0
2013-02-25T14:02:16.707Z
2013-02-28T23:48:13.647Z
2013-02-28T23:48:13.647Z
Andrej Bauer
<ol>
<li>How can we express "$P=PSPACE$" as a first-order formula?</li>
<li>Which level of the arithmetic hierarchy contains this formula (and what is the currently known minimum level of the hierarchy that contains it)?</li>
</ol>

<p>For reference, see <a href="http://rjlipton.wordpress.com/2009/05/27/arithmetic-hierarchy-and-pnp/">this blog post by Lipton</a>.</p>

CC BY-SA 3.0
2013-02-25T07:43:29.957Z
cross-posted from http://math.stackexchange.com/questions/313634/can-p-pspace-and-pspace-problems-be-formulated-as-pi-1-formula
mars
CC BY-SA 3.0
2013-02-25T08:53:28.347Z
Perhaps, you can use the same Lipton's proof using a PSPACE-complete problem instead of SAT in the definition of $\psi(x,c,y)$ and you get that $P \neq PSPACE$ can be expressed as $\forall x,c \; \exists y \; \psi(x,c,y)$ i.e. it is a $\Pi_2$ sentence. But IMO it is a kind of "hack" ... :-)
Marzio De Biasi
CC BY-SA 3.0
2013-02-25T10:36:09.297Z
I would bet my life and all worldly possessions that you can represent it as "False". That is, it's expressible even in propositional logic. :)
Shaull
CC BY-SA 3.0
2013-02-25T10:47:56.000Z
@Shaull. Sure. And once you show that this is the correct representation, you'll be able to buy all the possessions you need. Please don't protest that the comment space is too short to contain a proof.
Vijay D
CC BY-SA 3.0
2013-02-25T10:58:05.517Z
@VijayD - I'll take the bait: I have found a truly wonderful proof, and the comment space is sufficient. But I don't like the font...
Shaull
CC BY-SA 3.0
2013-02-25T20:40:57.443Z
Voting to close as an exact duplicate of the math stackexchange question.  Simultaneous cross-posting is strongly discouraged.
Jeffε
CC BY-SA 3.0
2013-02-25T21:36:34.437Z
It appears that you have crossposted ([copy](http://cs.stackexchange.com/q/10083) on [cs.se]) this question *simultaneously*. While we don't mind a question being reposted, our [site policy](http://meta.cstheory.stackexchange.com/a/231/) prohibits simultaneous crossposting as it duplicates effort and fractures discussion. Crossposting is only permitted after sufficient time has passed and you have not obtained your desired answer elsewhere. When crossposting please summarize the relevant discussions from other sites in your question and link to the copies in both directions.
Kaveh
<cc.complexity-theory><lo.logic><descriptive-complexity>
How can we express "$P=PSPACE$" as a first-order formula?
mars
# How can we express "$P=PSPACE$" as a first-order formula?

(Asked by: username_0 on 2013-02-25)

1. How can we express "$P=PSPACE$" as a first-order formula?
2. Which level of the arithmetic hierarchy contains this formula (and what is the currently known minimum level of the hierarchy that contains it)?

For reference, see [this blog post by Lipton](http://rjlipton.wordpress.com/2009/05/27/arithmetic-hierarchy-and-pnp/).

**Tags:** cc.complexity-theory, lo.logic, descriptive-complexity
> **Comments:**
> **username_0**: cross-posted from http://math.stackexchange.com/questions/313634/can-p-pspace-and-pspace-problems-be-formulated-as-pi-1-formula  
> **username_1**: Perhaps, you can use the same Lipton's proof using a PSPACE-complete problem instead of SAT in the definition of $\psi(x,c,y)$ and you get that $P \neq PSPACE$ can be expressed as $\forall x,c \; \exists y \; \psi(x,c,y)$ i.e. it is a $\Pi_2$ sentence. But IMO it is a kind of "hack" ... :-)  
> **username_2**: I would bet my life and all worldly possessions that you can represent it as "False". That is, it's expressible even in propositional logic. :)  
> **username_3**: @Shaull. Sure. And once you show that this is the correct representation, you'll be able to buy all the possessions you need. Please don't protest that the comment space is too short to contain a proof.  
> **username_2**: @VijayD - I'll take the bait: I have found a truly wonderful proof, and the comment space is sufficient. But I don't like the font...  
> **username_4**: Voting to close as an exact duplicate of the math stackexchange question.  Simultaneous cross-posting is strongly discouraged.  
> **username_5**: It appears that you have crossposted ([copy](http://cs.stackexchange.com/q/10083) on [cs.se]) this question *simultaneously*. While we don't mind a question being reposted, our [site policy](http://meta.cstheory.stackexchange.com/a/231/) prohibits simultaneous crossposting as it duplicates effort and fractures discussion. Crossposting is only permitted after sufficient time has passed and you have not obtained your desired answer elsewhere. When crossposting please summarize the relevant discussions from other sites in your question and link to the copies in both directions.  

---

## 2 answers

### Answer by username_8 on 2013-02-25. Score: 26 | Accepted answer

Firstly, I want to address the comments to the question, where it was suggested that "false" expresses $P = PSPACE$ because the statement *is* false. While this might be a good joke, it is actually very much harmful to think this way. When we ask how to express a certain sentence in a certain formal system, we are not talking about truth values. If we were, then when someone asked "How do I write down the fact that there are infinitely many primes?" we could answer "3 + 3 = 6", but this clearly will not do. For the same reason "false" is not a valid answer to "how do I write down $P = PSPACE$?". I think Frege and Russell tried hard to teach us that lesson. Ok, now to the answer.

Let me show how to express $PSPACE \subseteq P$, the other direction is similar, and then you can put them together in a conjunction to get $PSPACE = P$. In any case, for your purposes it may be sufficient to express just $PSPACE \subseteq P$, depending on what you are doing.

Using techniques similar to those in the construction of [Kleene's predicate $T$](http://en.wikipedia.org/wiki/Kleene%27s_T_predicate),
we can construct a bounded quantifer formula $accept\_{space}(k, m, n)$ (which thus resides in $\Sigma^0\_0 = \Pi^0\_0$) saying "when we run the machine encoded by $k$ and bound its space usage to $|n|^m$, the machine accepts the input $n$." Here $|n|$ is the length of $n$. An informal way of seeing that such formulas exists is this: given $k$, $m$, and $n$ we can compute primitive recursive bound on how much time and how much space we are ever going to need (i.e., at most $|n|^m$ space and at most $2^{|n|^m}$ time). We then simply search through all possible execution traces which are within the computed bounds--such a search is rather inefficient, but it is primitive recursive and so we can express it as a bounded formula.

There is a similar formula $accept\_{time}(k, m, n)$ in which the running time is bound by $|n|^m$.

Now consider the formula:
$$\forall k, m . \exists k', m' . \forall n .
accept\_{space}(k,m,n) \Leftrightarrow accept\_{time}(k',m', n).
$$
It says that for every machine $k$ which uses at most space $|n|^m$ there is a machine $k'$ which uses at most time $|n|^{m'}$ such that the two machines accepts exactly the same $n$'s. In other words, the formula says $PSPACE \subseteq P$. This formula is $\Pi^0\_3$.

We can improve this if we are willing to express instead the sentence "$TQBF$ is in polytime" , which should be good enough for most applications, as [TQBF](http://en.wikipedia.org/wiki/PSPACE-complete#TQBF) is PSPACE complete and so it being in polytime is equivalent to $PSPACE \subseteq P$. Let $k\_0$ be (the code of) a machine which recognizes TQBF in space $|n|^{m\_0}$. Then "$TQBF \in P$" can be expressed as
$$\exists k', m' . \forall n . accept\_{space}(k\_0, m\_0, n) \Leftrightarrow accept\_{time}(k', m', n).$$
This formula is just $\Sigma^0\_2$. If I were a complexity theorist I would know if it is possible to do even better (but I doubt it).

> **Comments:**
> **username_3**: your first paragraph is almost like a logical, textual form of this: http://xkcd.com/169/  

---

### Answer by username_6 on 2013-02-25. Score: 21

Andrej has already explained that $P=\mathit{PSPACE}$ can be written as a $\Sigma^0\_2$-sentence. Let me mention that this classification is optimal in the sense that if the statement is equivalent to a $\Pi^0\_2$-sentence, then this fact does not relativize. More precisely, the set of oracles $A$ such that $P^A=\mathit{PSPACE}^A$ is definable by a $\Sigma^0\_2$-formula with a free second-order variable $A$, but it is not definable by any $\Pi^0\_2$-formula. The argument is outlined (for $P=\mathit{NP}$, but it works just the same for $\mathit{PSPACE}$) in the comments at <https://mathoverflow.net/questions/57348>. (In fact, one can show by an elaboration of the idea that the set is $\Sigma^0\_2$-complete in the appropriate sense.)

EDIT: The topological proof given in the linked comment is short, but it may appear tricky. Here is a direct forcing argument.

$P^A\ne\mathit{PSPACE}^A$ can be written as a $\Pi^0\_2$-formula of the form $\phi(A)=\forall x\,\exists y\,\theta(A,x,y)$, where $\theta$ is $\Delta^0\_0$. Assume for contradiction that $P^A=\mathit{PSPACE}^A$ is also equivalent to a $\Pi^0\_2$-formula $\psi(A)=\forall x\,\exists z\,\eta(A,x,z)$. Fix oracles $B$, $C$ such that $P^B\ne\mathit{PSPACE}^B$ and $P^C=\mathit{PSPACE}^C$.

Since $\phi(B)$, there exists $y\_0$ such that $\theta(B,0,y\_0)$. However, $\theta$ is a bounded formula, hence the evaluation of the truth value of $\theta(B,0,y\_0)$ only uses a finite part of the oracle. Thus, there exists a finite part $b\_0$ of $B$ such that $\theta(A,0,y\_0)$ for every oracle $A$ extending $b\_0$.

Let $C[b\_0]$ denote the oracle which extends $b\_0$, and agrees with $C$ where $b\_0$ is undefined. Since $P^A$ and $\mathit{PSPACE}^A$ are unaffected by a finite change in the oracle, we have $\psi(C[b\_0])$. By the same argument as above, there exists $z\_0$ and a finite part $c\_0$ of $C[b\_0]$ such that $\eta(A,0,z\_0)$ for every $A$ extending $c\_0$. We may assume that $c\_0$ extends $b\_0$.

Continuing in the same fashion, we construct infinite sequences of numbers $y\_0,y\_1,y\_2,\dots$, $z\_0,z\_1,z\_2,\dots$, and finite partial oracles $b\_0\subseteq c\_0\subseteq b\_1\subseteq c\_1\subseteq b\_2\subseteq\cdots$ such that

1. $\theta(A,n,y\_n)$ for every oracle $A$ extending $b\_n$,
2. $\eta(A,n,z\_n)$ for every oracle $A$ extending $c\_n$.

Now, let $A$ be an oracle which extends all $b\_n$ and $c\_n$. Then 1 and 2 imply that $\phi(A)$ and $\psi(A)$ simultaneously hold, which contradicts the assumption that they are complements of each other.

> **Comments:**
> **username_7**: Sad that such a nice answer is for a question that's now closed...  

---

