An Axiomatic Approach to Algebrization

Non-relativization of complexity issues can be interpreted as giving some evidence that these issues cannot be resolved by "black-box" techniques. In the early 1990's, a sequence of important non-relativizing results was proved, mainly using algebraic techniques. Two approaches have been proposed to understand the power and limitations of these algebraic techniques: (1) Fortnow gives a construction of a class of oracles which have a similar algebraic and logical structure, although they are arbitrarily powerful. He shows that many of the non-relativizing results proved using algebraic techniques hold for all such oracles, but he does not show, e.g., that the outcome of the "P vs. NP" question differs between different oracles in that class. (2) Aaronson and Wigderson give definitions of algebrizing separations and collapses of complexity classes, by comparing classes relative to one oracle to classes relative to an algebraic extension of that oracle. Using these definitions, they show both that the standard collapses and separations "algebrize" and that many of the open questions in complexity fail to "algebrize", suggesting that the arithmetization technique is close to its limits. However, it is unclear how to formalize algebrization of more complicated complexity statements than collapses or separations, and whether the algebrizing statements are, e.g., closed under modus ponens; so it is conceivable that several algebrizing premises could imply (in a relativizing way) a non-algebrizing conclusion. Here, building on the work of Arora, Impagliazzo, and Vazirani [4], we propose an axiomatic approach to "algebrization", which complements and clarifies the approaches of Fortnow and Aaronso&Wigderson. We present logical theories formalizing the notion of algebrizing techniques so that most algebrizing results are provable within our theories and separations requiring non-algebrizing techniques are independent of them. Our theories extend the [AIV] theory formalizing relativization by adding an Arithmetic Checkability axiom. We show the following: (i) Arithmetic checkability holds relative to arbitrarily powerful oracles (since Fortnow's algebraic oracles all satisfy Arithmetic Checkability axiom); by contrast, Local Checkability of [AIV] restricts the oracle power to NP cap co-NP. (ii) Most of the algebrizing collapses and separations from [AW], such as IP = PSPACE, NP subset ZKIP if one-way functions exist, MA-EXP not in P/poly, etc., are provable from Arithmetic Checkability. (iii) Many of the open complexity questions (shown to require nonalgebrizing techniques in [AW]), such as "P vs. NP", "NP vs. BPP", etc., cannot be proved from Arithmetic Checkability. (iv) Arithmetic Checkability is also insufficient to prove one known result, NEXP = MIP.