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 impor-tant non-relativizing results concerning “non-controversially relativizable ” complexity classes was proved, mainly using algebraic techniques. Two approaches have been proposed to under-stand the power and limitations of these algebraic techniques: (1) Fortnow [For94] 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 Wigder-son [AW08a] 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 “al-gebrize ” 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 alge