Abstract
Any proof of P ≠ NP will have to overcome two barriers: relativization and natural proofs. Yet over the last decade, we have seen circuit lower bounds (e.g., that PP does not have linear-size circuits) that overcome both barriers simultaneously. So the question arises of whether there is a third barrier to progress on the central questions in complexity theory.
In this article, we present such a barrier, which we call algebraic relativization or algebrization. The idea is that, when we relativize some complexity class inclusion, we should give the simulating machine access not only to an oracle A, but also to a low-degree extension of A over a finite field or ring.
We systematically go through basic results and open problems in complexity theory to delineate the power of the new algebrization barrier. First, we show that all known nonrelativizing results based on arithmetization---both inclusions such as IP = PSPACE and MIP = NEXP, and separations such as MAEXP ⊄ P/poly---do indeed algebrize. Second, we show that almost all of the major open problems---including P versus NP, P versus RP, and NEXP versus P/poly---will require non-algebrizing techniques. In some cases, algebrization seems to explain exactly why progress stopped where it did: for example, why we have superlinear circuit lower bounds for PromiseMA but not for NP.
Our second set of results follows from lower bounds in a new model of algebraic query complexity, which we introduce in this article and which is interesting in its own right. Some of our lower bounds use direct combinatorial and algebraic arguments, while others stem from a surprising connection between our model and communication complexity. Using this connection, we are also able to give an MA-protocol for the Inner Product function with O (√nlogn) communication (essentially matching a lower bound of Klauck), as well as a communication complexity conjecture whose truth would imply NL ≠ NP.
- Aaronson, S. 2006. Oracles are subtle but not malicious. In Proceedings of the IEEE Conference on Computational Complexity. IEEE Computer Society Press, Los Alamitos, CA. 340--354. Google ScholarDigital Library
- Arora, S., Impagliazzo, R., and Vazirani, U. 1992. Relativizing versus nonrelativizing techniques: The role of local checkability. (http://www.cs.berkeley.edu/~vazirani/pubs/relativizing.ps).Google Scholar
- Babai, L., Fortnow, L., and Lund, C. 1991. Nondeterministic exponential time has two-prover interactive protocols. Computat. Complex. 1, 1, 3--40.Google ScholarCross Ref
- Baker, T., Gill, J., and Solovay, R. 1975. Relativizations of the P=?NP question. SIAM J. Comput. 4, 431--442.Google ScholarDigital Library
- Bennett, C. H. and Gill, J. 1981. Relative to a random oracle A, P A ≠ NP A ≠ coNP A with probability 1. SIAM J. Comput. 10, 1, 96--113.Google ScholarCross Ref
- Buhrman, H., Fortnow, L., and Thierauf, T. 1998. Nonrelativizing separations. In Proceedings of the IEEE Conference on Computational Complexity. IEEE Computer Society Press, Los Alamitos, CA, 8--12. Google ScholarDigital Library
- Buhrman, H., Vereshchagin, N., and de Wolf, R. 2007. On computation and communication with small bias. In Proceedings of the IEEE Conference on Computational Complexity. IEEE Computer Society Press, Los Alamitos, CA, 24--32. Google ScholarDigital Library
- Buhrman, H. and de Wolf, R. 2002. Complexity measures and decision tree complexity: A survey. Theoret. Comput. Sci. 288, 21--43. Google ScholarDigital Library
- Feige, U. and Kilian, J. 1997. Making games short. In Proceedings of the ACM Annual Symposium on Theory of Computing. ACM, New York. 506--516. Google ScholarDigital Library
- Fortnow, L. 1994. The role of relativization in complexity theory. Bull. EATCS 52, 229--244.Google Scholar
- Furst, M., Saxe, J. B., and Sipser, M. 1984. Parity, circuits, and the polynomial time hierarchy. Math. Syst. Theory 17, 13--27.Google ScholarCross Ref
- Goldreich, O., Micali, S., and Wigderson, A. 1991. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM 38, 1, 691--729. Google ScholarDigital Library
- Hartmanis, J., Chang, R., Chari, S., Ranjan, D., and Rohatgi, P. 1992. Relativization: A revisionistic perspective. Bull. EATCS 47, 144--153.Google Scholar
- Hartmanis, J. and Stearns, R. E. 1965. On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117, 285--306.Google ScholarCross Ref
- Hopcroft, J. E., Paul, W. J., and Valiant, L. G. 1977. On time versus space. J. ACM 24, 2, 332--337. Google ScholarDigital Library
- Impagliazzo, R., Kabanets, V., and Wigderson, A. 2002. In search of an easy witness: Exponential time vs. probabilistic polynomial time. J. Comput. Syst. Sci. 65, 4, 672--694. Google ScholarDigital Library
- Juma, A., Kabanets, V., Rackoff, C., and Shpilka, A. 2007. The black-box query complexity of polynomial summation. ECCC TR07-125.Google Scholar
- Kalyanasundaram, B. and Schnitger, G. 1992. The probabilistic communication complexity of set intersection. SIAM J. Discrete Math 5, 4, 545--557. Google ScholarDigital Library
- Kannan, R. 1982. Circuit-size lower bounds and non-reducibility to sparse sets. Inf. Cont. 55, 40--56.Google ScholarCross Ref
- Karchmer, M. and Wigderson, A. 1990. Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Comput. 3, 255--265.Google Scholar
- Klauck, H. 2003. Rectangle size bounds and threshold covers in communication complexity. In Proceedings of the IEEE Conference on Computational Complexity. IEEE Computer Society Press, Los Alamitos, CA. 118--134. cs.CC/0208006.Google ScholarCross Ref
- Klivans, A. and van Melkebeek, D. 2002. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM J. Comput. 31, 1501--1526. (Earlier version in Proceedings of the ACM Annual Symposium on Theory of Computing) 1999. Google ScholarDigital Library
- Lund, C., Fortnow, L., Karloff, H., and Nisan, N. 1992. Algebraic methods for interactive proof systems. J. ACM 39, 859--868. Google ScholarDigital Library
- Paul, W. J., Pippenger, N., Szemerédi, E., and Trotter, W. T. 1983. On determinism versus non-determinism and related problems. In Proceedings of the IEEE Conference on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA. 429--438. Google ScholarDigital Library
- Raz, R. 1999. Exponential separation of quantum and classical communication complexity. In Proceedings of the ACM Symposium on Theory of Computing. ACM, New York. 358--367. Google ScholarDigital Library
- Raz, R. and Shpilka, A. 2004. On the power of quantum proofs. In Proceedigns of the IEEE Conference on Computational Complexity. IEEE Computer Society Press, Los Alamitos, CA. 260--274. Google ScholarDigital Library
- Razborov, A. A. 1987. Lower bounds for the size of circuits of bounded depth with basis {&,⊕⊕}. Mathematicheskie Zametki 41, 4, 598--607. (English translation in Math. Notes. Acad. Sci. USSR 41, 4, 1987) 333--338.Google Scholar
- Razborov, A. A. 1992. On the distributional complexity of disjointness. Theoret. Comput. Sci. 106, 385--390. Google ScholarDigital Library
- Razborov, A. A. 2003. Quantum communication complexity of symmetric predicates. Izvestiya Math. (English version) 67, 1, 145--159. quant-ph/0204025.Google Scholar
- Razborov, A. A. and Rudich, S. 1997. Natural proofs. J. Comput. Sys. Sci. 55, 1, 24--35. Google ScholarDigital Library
- Santhanam, R. 2007. Circuit lower bounds for Merlin-Arthur classes. In Proceedings of the ACM Symposium on Theory of Computing. ACM, New York. 275--283. Google ScholarDigital Library
- Shamir, A. 1992. IP=PSPACE. J. ACM 39, 4, 869--877. Google ScholarDigital Library
- Smolensky, R. 1987. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings of the ACM Symposium on Theory of Computing. ACM, New York. 77--82. Google ScholarDigital Library
- Toda, S. 1991. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20, 5, 865--877. Google ScholarDigital Library
- Trevisan, L. and Vadhan, S. 2002. Pseudorandomness and average-case complexity via uniform reductions. In Proceedings of the IEEE Conference on Computational Complexity. IEEE Computer Society Press, Los Alamitos, CA. 129--138. Google ScholarDigital Library
- van Melkebeek, D. 2007. A survey of lower bounds for satisfiability and related problems. Foundations and Trends in Theoretical Computer Science 2, 197--303. ECCC TR07-099. Google ScholarDigital Library
- Vinodchandran, N. V. 2004. A note on the circuit complexity of PP. ECCC TR04-056.Google Scholar
- Wigderson, A. 1990. Information theoretic reasons for computational difficulty. In Proceedings of the International Congress of Mathematicians. 1537--1548.Google Scholar
- Yao, A. C.-C. 1985. Separating the polynomial-time hierarchy by oracles (preliminary version). In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA. 1--10. Google ScholarDigital Library
- Yao, A. C.-C. 1986. How to generate and exchange secrets (extended abstract). In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA. 162--167. Google ScholarDigital Library
Index Terms
- Algebrization: A New Barrier in Complexity Theory
Recommendations
Algebrization: a new barrier in complexity theory
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingAny proof of P!=NP will have to overcome two barriers: relativization and natural proofs. Yet over the last decade, we have seen circuit lower bounds (for example, that PP does not have linear-size circuits) that overcome both barriers simultaneously. ...
The relativized relationship between probabilistically checkable debate systems, IP and PSPACE
In 1990, PSPACE was shown to be identical to IP, the class of languages with interactive proofs [18,20]. Recently, PSPACE was again recharacterized, this time in terms of (Random) Probabilistically Checkable Debate Systems [7,8]. In particular, it was ...
An axiomatic approach to algebrization
STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computingNon-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 ...
Comments