Impagliazzo, Russell ;
Kabanets, Valentine ;
Kolokolova, Antonina
An Axiomatic Approach to Algebrization
Abstract
Nonrelativization of complexity issues can be interpreted
as giving some evidence that these issues cannot be resolved
by "blackbox" techniques. In the early 1990's, a sequence of
important nonrelativizing 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 nonrelativizing 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 nonalgebrizing 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
nonalgebrizing 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 coNP. (ii) Most of the algebrizing
collapses and separations from [AW], such as IP = PSPACE,
NP subset ZKIP if oneway functions exist, MAEXP 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.
BibTeX  Entry
@InProceedings{impagliazzo_et_al:DSP:2010:2415,
author = {Russell Impagliazzo and Valentine Kabanets and Antonina Kolokolova},
title = {An Axiomatic Approach to Algebrization},
booktitle = {Algebraic Methods in Computational Complexity},
year = {2010},
editor = {Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans},
number = {09421},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Schloss Dagstuhl  LeibnizZentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2415},
annote = {Keywords: Oracles, arithmetization, algebrization}
}
Keywords: 

Oracles, arithmetization, algebrization 
Seminar: 

09421  Algebraic Methods in Computational Complexity

Issue date: 

2010 
Date of publication: 

19.01.2010 