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