Name
Abstract | ||
|---|---|---|
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 (12) gives a construction of a class of oracles which have a similar algebraic and logical struc- ture, 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 diers between dierent oracles in that class. (2) Aaronson and Wigderson (1) 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. In this paper, building on the work of Arora, Impagliazzo, and Vazirani (4), we propose an axiomatic approach to"alge- brization", which complements and clarifies the approaches of (12) and (1). 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 Work partially supported by NSF grants 0835373 and 0832797 and the Ellentuck Foundation † Work partially supported by NSERC Discovery grant ‡ Work partially supported by NSERC Discovery grant |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1145/1536414.1536509 | 2986012532 |
Keywords | Field | DocType |
complexity issue,axiomatic approach,independence,open question,complexity class,arithmetic checkability axiom,algebraic oracle,arithmetization technique,complicated complexity statement,arithmetic checkability,algebraic extension,algebrization,relativization,algebraic technique,modus ponens | NEXPTIME,Integer,Complexity class,Discrete mathematics,Combinatorics,Modus ponens,Computer science,Axiom,Oracle,PSPACE,Algebraic extension | Conference |
ISSN | Citations | PageRank |
0737-8017 | 7 | 0.46 |
References | Authors | |
22 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Russell Impagliazzo | 1 | 5444 | 482.13 |
| Valentine Kabanets | 2 | 562 | 35.38 |
| Antonina Kolokolova | 3 | 50 | 10.09 |