9
$\begingroup$
  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.

$\endgroup$
7
  • 1
    $\begingroup$ cross-posted from math.stackexchange.com/questions/313634/… $\endgroup$
    – mars
    Feb 25, 2013 at 7:43
  • 1
    $\begingroup$ 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" ... :-) $\endgroup$ Feb 25, 2013 at 8:53
  • 3
    $\begingroup$ 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. :) $\endgroup$
    – Shaull
    Feb 25, 2013 at 10:36
  • 3
    $\begingroup$ @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. $\endgroup$
    – Vijay D
    Feb 25, 2013 at 10:47
  • 3
    $\begingroup$ @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... $\endgroup$
    – Shaull
    Feb 25, 2013 at 10:58

2 Answers 2

26
$\begingroup$

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$, 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 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).

$\endgroup$
1
  • $\begingroup$ your first paragraph is almost like a logical, textual form of this: xkcd.com/169 $\endgroup$
    – Vijay D
    Feb 28, 2013 at 19:31
21
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ Sad that such a nice answer is for a question that's now closed... $\endgroup$
    – arnab
    Mar 1, 2013 at 7:00

Not the answer you're looking for? Browse other questions tagged or ask your own question.