An axiomatic approach to algebrization

Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova


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:

In this paper, building on the work of Arora, Impagliazzo, and Vazirani, we propose an axiomatic approach to ``algebrization'', which complements and clarifies the approaches of Fortnow and Aaronson&Wigderson. We present logical theories formalizing the notion of algebrizing techniques in the following sense: most known complexity results proved using arithmetization are provable within our theories, while many open questions are independent of the theories. So provability in the proposed theories can serve as a surrogate for provability using the arithmetization technique.

Our theories extend the Arora et al.'s theory with a new axiom, Arithmetic Checkability which intuitively says that all NP languages have verifiers that are efficiently computable low-degree polynomials (over the integers). We show the following: