<p>Any answer to a question of the form, "What is the <i>real</i> reason that..." will necessarily be somewhat subjective.  However, for the particular case of IP = PSPACE, I think that a pretty good case can be made that arithmetization is indeed the key, by observing that while IP = PSPACE does not <i>relativize</i>, it does <i>algebrize</i> in the sense of <a href="http://www.scottaaronson.com/papers/alg.ps">Aaronson and Wigderson</a>.  As they explain in their paper, roughly speaking, a complexity class inclusion ${\cal C} \subseteq {\cal D}$ <i>algebrizes</i> if ${\cal C}^A \subseteq {\cal D}^{\tilde A}$ for all oracles $A$ and all low-degree extensions $\tilde A$ of $A$.  In particular, they show that the inclusion PSPACE $\subseteq$ IP algebrizes, even though it doesn't relativize.</p>

<blockquote>
  <p>The intuition that I've developed is that non-relativizing results are ones that poke around with the nitty gritty of Turing Machines</p>
</blockquote>

<p>This is not a bad intuition, but I think that the Aaronson-Wigderson result shows that the IP = PSPACE proof pokes around in a rather limited way, and certainly not in a sophisticated enough way to prove P $\ne$ NP, since Aaronson and Wigderson also show that non-algebrizing techniques will be required to separate P from NP.</p>

CC BY-SA 3.0
2012-01-27T21:58:13.500Z
Thanks for the reference. Let me see if I understand this: what you - and the Aaronson/Wigderson paper - seem to be arguing is that "arithmetization" is a *weakly* non-relativizing step, and that a tiny, natural change to the notion of relativization (namely, algebraic relativization) will break this property.

Since the rest of the IP=PSPACE proof is relativizing (and I am convinced by what Emil said above), that means the IP=PSPACE result itself is very weakly non-relativizing, which is what you said. 

Very interesting! Thanks. I need a way of accepting both answers :)
Henry Yuen
CC BY-SA 3.0
2012-01-27T23:45:51.547Z
Yes, that's basically right.
Timothy Chow
CC BY-SA 3.0
2012-01-27T19:53:05.663Z
2012-01-27T19:53:05.663Z
Timothy Chow
<p>IP=PSPACE is listed as the canonical example of a non-relativizing result, and the proof for this is that there exists an oracle $O$ such that ${\sf coNP}^O \not\subseteq {\sf IP}^O$, while ${\sf coNP}^O \subseteq {\sf PSPACE}^O$ for all oracles $O$.</p>

<p>However, I've seen only a few people give a "direct" explanation for why the ${\sf IP} = {\sf PSPACE}$ result does not relativize, and the usual answer is "arithmetization". Upon inspection of the proof of IP=PSPACE, that answer isn't <em>false</em>, but it isn't satisfactory to me. It seems that the "real" reason traces itself back to the proof that the problem TQBF - true quantified boolean formula - is complete for PSPACE; to prove that, you need to show that you can encode configurations of a PSPACE machine in a polynomial-sized format, and (this seems to be the non-relativizing part) you can encode "correct" transitions between configurations in a polynomial-sized boolean formula - this uses a Cook-Levin-style step.</p>

<p>The intuition that I've developed is that non-relativizing results are ones that poke around with the nitty gritty of Turing Machines, and the step where TQBF is shown to be complete for PSPACE is where this poking around happens - and the arithmetization step could've only happened because you had an explicit boolean formula to arithmetize.</p>

<p>This appears to me to be the fundamental reason that IP=PSPACE is non-relativizing; and the folklore mantra that arithmetization techniques don't relativize seems to be a byproduct of that: the only way to arithmetize something is if you have a boolean formula that encodes something about TMs in the first place! </p>

<p>Is there something I'm missing? As a subquestion - does this mean all results that use TQBF in some way also do not relativize?</p>

CC BY-SA 3.0
2012-01-27T12:14:58.590Z
You can include oracle gates in a quantified Boolean formula, and then such a relativized TQBF^O is complete for PSPACE^O, so this is not the non-relativizing step.
Emil Jeřábek
CC BY-SA 3.0
2012-01-27T17:02:42.327Z
Hi Emil - could you elaborate a little more? Let's say I have a ${\sf PSPACE}^O$ machine M, and I try to carry out the same proof that L(M) (the language accepted by M) is reducible to  $TBQF^O$ (whatever $TBQF^O$ means). I eventually will have to come up with a boolean formula that expresses whether two configurations C,C' of the oracle machine M are neighbors (for any two configurations C,C'). How can I ensure, regardless of the oracle, this boolean formula has finite size, let alone polynomial sized? For example, O could encode the Halting Problem.
Henry Yuen
CC BY-SA 3.0
2012-01-27T17:21:25.060Z
I guess I could push this back even further - does the Cook-Levin theorem *itself* relativize? For the same reasons mentioned above, I don't think it does. Whether the Cook-Levin theorem relativizes determines whether the PSPACE-completeness proof of TQBF also relativizes.
Henry Yuen
CC BY-SA 3.0
2012-01-27T17:51:35.597Z
A QBF^O formula can, apart from the usual quantifiers and Boolean connectives, also use a new unbounded fan-in gate, let's call it $f(x_0,\dots,x_n)$, whose semantics is that $f(x_0,\dots,x_n)=1$ iff the string $x_0\dots x_n$ belongs to the oracle $O$. Expressing in this language that one configuration is a successor of another is a simple exercise, since you can just plug the content of the oracle query tape into $f$. (I’m assuming here that a PSPACE machine can only make polynomially long queries.)
Emil Jeřábek
CC BY-SA 3.0
2012-01-27T20:28:06.827Z
I see - you're saying that when relativizing the proof of PSPACE-completeness of TQBF, not only do you relativize the machines in play, but you also relativize the boolean formulas themselves (so they're no longer boolean formulas in the strict sense). In that case, I can see why the arithmetization step would break down. Thanks! Perhaps you can write it as an answer.
Henry Yuen
<cc.complexity-theory><interactive-proofs><relativization>
What's the "real" reason that IP=PSPACE is non-relativizing?
Henry Yuen
# What's the "real" reason that IP=PSPACE is non-relativizing?

(Asked by: username_0 on 2012-01-27)

IP=PSPACE is listed as the canonical example of a non-relativizing result, and the proof for this is that there exists an oracle $O$ such that ${\sf coNP}^O \not\subseteq {\sf IP}^O$, while ${\sf coNP}^O \subseteq {\sf PSPACE}^O$ for all oracles $O$.

However, I've seen only a few people give a "direct" explanation for why the ${\sf IP} = {\sf PSPACE}$ result does not relativize, and the usual answer is "arithmetization". Upon inspection of the proof of IP=PSPACE, that answer isn't *false*, but it isn't satisfactory to me. It seems that the "real" reason traces itself back to the proof that the problem TQBF - true quantified boolean formula - is complete for PSPACE; to prove that, you need to show that you can encode configurations of a PSPACE machine in a polynomial-sized format, and (this seems to be the non-relativizing part) you can encode "correct" transitions between configurations in a polynomial-sized boolean formula - this uses a Cook-Levin-style step.

The intuition that I've developed is that non-relativizing results are ones that poke around with the nitty gritty of Turing Machines, and the step where TQBF is shown to be complete for PSPACE is where this poking around happens - and the arithmetization step could've only happened because you had an explicit boolean formula to arithmetize.

This appears to me to be the fundamental reason that IP=PSPACE is non-relativizing; and the folklore mantra that arithmetization techniques don't relativize seems to be a byproduct of that: the only way to arithmetize something is if you have a boolean formula that encodes something about TMs in the first place!

Is there something I'm missing? As a subquestion - does this mean all results that use TQBF in some way also do not relativize?

**Tags:** cc.complexity-theory, interactive-proofs, relativization

> **Comments:**
> **username_1**: You can include oracle gates in a quantified Boolean formula, and then such a relativized TQBF^O is complete for PSPACE^O, so this is not the non-relativizing step.  
> **username_0**: Hi Emil - could you elaborate a little more? Let's say I have a ${\sf PSPACE}^O$ machine M, and I try to carry out the same proof that L(M) (the language accepted by M) is reducible to  $TBQF^O$ (whatever $TBQF^O$ means). I eventually will have to come up with a boolean formula that expresses whether two configurations C,C' of the oracle machine M are neighbors (for any two configurations C,C'). How can I ensure, regardless of the oracle, this boolean formula has finite size, let alone polynomial sized? For example, O could encode the Halting Problem.  
> **username_0**: I guess I could push this back even further - does the Cook-Levin theorem *itself* relativize? For the same reasons mentioned above, I don't think it does. Whether the Cook-Levin theorem relativizes determines whether the PSPACE-completeness proof of TQBF also relativizes.  
> **username_1**: A QBF^O formula can, apart from the usual quantifiers and Boolean connectives, also use a new unbounded fan-in gate, let's call it $f(x_0,\dots,x_n)$, whose semantics is that $f(x_0,\dots,x_n)=1$ iff the string $x_0\dots x_n$ belongs to the oracle $O$. Expressing in this language that one configuration is a successor of another is a simple exercise, since you can just plug the content of the oracle query tape into $f$. (I’m assuming here that a PSPACE machine can only make polynomially long queries.)  
> **username_0**: I see - you're saying that when relativizing the proof of PSPACE-completeness of TQBF, not only do you relativize the machines in play, but you also relativize the boolean formulas themselves (so they're no longer boolean formulas in the strict sense). In that case, I can see why the arithmetization step would break down. Thanks! Perhaps you can write it as an answer.  

---

## 1 answers

### Answer by username_2 on 2012-01-27. Score: 13 | Accepted answer

Any answer to a question of the form, "What is the *real* reason that..." will necessarily be somewhat subjective. However, for the particular case of IP = PSPACE, I think that a pretty good case can be made that arithmetization is indeed the key, by observing that while IP = PSPACE does not *relativize*, it does *algebrize* in the sense of [Aaronson and Wigderson](http://www.scottaaronson.com/papers/alg.ps). As they explain in their paper, roughly speaking, a complexity class inclusion ${\cal C} \subseteq {\cal D}$ *algebrizes* if ${\cal C}^A \subseteq {\cal D}^{\tilde A}$ for all oracles $A$ and all low-degree extensions $\tilde A$ of $A$. In particular, they show that the inclusion PSPACE $\subseteq$ IP algebrizes, even though it doesn't relativize.

> The intuition that I've developed is that non-relativizing results are ones that poke around with the nitty gritty of Turing Machines

This is not a bad intuition, but I think that the Aaronson-Wigderson result shows that the IP = PSPACE proof pokes around in a rather limited way, and certainly not in a sophisticated enough way to prove P $\ne$ NP, since Aaronson and Wigderson also show that non-algebrizing techniques will be required to separate P from NP.

> **Comments:**
> **username_0**: Thanks for the reference. Let me see if I understand this: what you - and the Aaronson/Wigderson paper - seem to be arguing is that "arithmetization" is a *weakly* non-relativizing step, and that a tiny, natural change to the notion of relativization (namely, algebraic relativization) will break this property.  Since the rest of the IP=PSPACE proof is relativizing (and I am convinced by what Emil said above), that means the IP=PSPACE result itself is very weakly non-relativizing, which is what you said.   Very interesting! Thanks. I need a way of accepting both answers :)  
> **username_2**: Yes, that's basically right.  

---

