21
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Jan 27, 2012 at 12:14
  • $\begingroup$ 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. $\endgroup$
    – Henry Yuen
    Jan 27, 2012 at 17:02
  • $\begingroup$ 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. $\endgroup$
    – Henry Yuen
    Jan 27, 2012 at 17:21
  • 4
    $\begingroup$ 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.) $\endgroup$
    – Emil Jeřábek
    Jan 27, 2012 at 17:51
  • $\begingroup$ 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. $\endgroup$
    – Henry Yuen
    Jan 27, 2012 at 20:28

1 Answer 1

Reset to default
13
$\begingroup$

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. 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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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 :) $\endgroup$
    – Henry Yuen
    Jan 27, 2012 at 21:58
  • $\begingroup$ Yes, that's basically right. $\endgroup$
    – Timothy Chow
    Jan 27, 2012 at 23:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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