Arithmetization: A new method in structural complexity theory.

*(English)*Zbl 0774.68040Summary: We introduce a technique of arithmetization of the process of computation in order to obtain novel characterization of certain complexity classes via multivariate polynomials. A variety of concepts and tools of elementary algebras, such as the degree of polynomials and interpolation, becomes thereby available for the study of complexity classes.

The theory to be described provides a unified framework from which powerful recent results follow naturally.

The central result is a characterization of \(\#P\) in terms of arithmetic straight line programs. The consequences include a simplified proof of Toda’s theorem [S. Toda, On the computational power of \(PP\) and \(\oplus P\), in Proc. 30th Ann. IEEE Symp. Foundations of Comp. Sci., 514- 519 (1989)] that \(PH\subseteq P^{\#P}\); and an infinite class of natural and potential inequivalent functions, checkable in the sense of M. Blum [Designing programs that check their work, submitted to Comm. of Assoc. Comput. Mach.], M. Blum and S.Kannan [Designing programs that check their work, in Proc. 21st Ann. ACM Symp. Theory of Computing, 86-97 (1989)], and M. Blum, M. Luby and R. Rubinfeld [Self-testing and self-correcting programs, with applications to numerical programs, in Proc. 22nd Ann. ACM Symp. Theory of Computing, 73-83 (1990)]. Similar characterizations of PSPACE are also given.

The arithmetization technique has been introduced independently by A. Sharmir [IP=PSPACE, in Proc. 31st Ann. IEEE Symp. Foundations of Comp. Sci., 11-15 (1990)]. While this simultaneous discovery was driven by applications to interactive proofs, the present paper demonstrates the applicability of this technique to classical complexity classes.

The theory to be described provides a unified framework from which powerful recent results follow naturally.

The central result is a characterization of \(\#P\) in terms of arithmetic straight line programs. The consequences include a simplified proof of Toda’s theorem [S. Toda, On the computational power of \(PP\) and \(\oplus P\), in Proc. 30th Ann. IEEE Symp. Foundations of Comp. Sci., 514- 519 (1989)] that \(PH\subseteq P^{\#P}\); and an infinite class of natural and potential inequivalent functions, checkable in the sense of M. Blum [Designing programs that check their work, submitted to Comm. of Assoc. Comput. Mach.], M. Blum and S.Kannan [Designing programs that check their work, in Proc. 21st Ann. ACM Symp. Theory of Computing, 86-97 (1989)], and M. Blum, M. Luby and R. Rubinfeld [Self-testing and self-correcting programs, with applications to numerical programs, in Proc. 22nd Ann. ACM Symp. Theory of Computing, 73-83 (1990)]. Similar characterizations of PSPACE are also given.

The arithmetization technique has been introduced independently by A. Sharmir [IP=PSPACE, in Proc. 31st Ann. IEEE Symp. Foundations of Comp. Sci., 11-15 (1990)]. While this simultaneous discovery was driven by applications to interactive proofs, the present paper demonstrates the applicability of this technique to classical complexity classes.

##### MSC:

68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |

68Q60 | Specification and verification (program logics, model checking, etc.) |

PDF
BibTeX
XML
Cite

\textit{L. Babai} and \textit{L. Fortnow}, Comput. Complexity 1, No. 1, 41--66 (1991; Zbl 0774.68040)

Full Text:
DOI

**OpenURL**

##### References:

[1] | L. Babai, Trading group theory for randomness, inProc. 17th Ann. ACM Symp. Theory of Computing, 1985, 421-429. |

[2] | L. Babai, E-mail and the unexpected power of interaction, inProc. 5th Ann. IEEE Structures in Complexity Theory Conf., 1990, 30-44. |

[3] | L. Babai and L. Fortnow, A characterization of #P by arithmetic straight line programs, inProc. 31st Ann. IEEE Symp. Foundations of Comp. Sci., 1990, 26-34. |

[4] | L. Babai, L. Fortnow, andC. Lund, Nondeterministic exponential time has two-prover interactive protocols,Computational Complexity 1 (1991), 3-40. Extended Abstract inProc. 31st Ann. IEEE Symp. Foundations of Comp. Sci., 1990, 16-25. · Zbl 0774.68041 |

[5] | L. Babai andS. Moran, Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes,Journal Comp. Sys. Sci. 36 (1988), 254-276. · Zbl 0652.03029 |

[6] | D. Beaver and J. Feigenbaum, Hiding instances in multioracle queries, inProc. 7th Symp. on Theoretical Aspects of Comp. Sci., Lecture Notes in Comp. Sci. 415 (1990), 37-48. · Zbl 0733.68005 |

[7] | R. Beigel, J. Gill, and U. Hertrampf, Counting classes: thresholds, parity, mods, and fewness, inProc. 7th Symp. on Theoretical Aspects of Comp. Sci., Lecture Notes in Comp. Sci. 415 (1990), 49-57. · Zbl 0729.68023 |

[8] | M. Blum, Designing programs that check their work, submitted toComm. of Assoc. Comput. Mach. |

[9] | M. Blum and S. Kannan, Designing programs that check their work, inProc. 21st Ann. ACM Symp. Theory of Computing, 1989, 86-97. |

[10] | M. Blum, M. Luby, and R. Rubinfeld, Self-testing and self-correcting programs, with applications to numerical programs, inProc. 22nd Ann. ACM Symp. Theory of Computing, 1990, 73-83. |

[11] | R. Beigel, N. Reingold and D. Spielman, PP is Closed under Intersection, inProc. 23rd Ann. ACM Symp. Theory of Computing, 1991, to appear. · Zbl 0827.68040 |

[12] | A. Chandra, D. Kozen, andL. Stockmeyer, Alternation,J. Assoc. Comput. Mach 28 (1981), 114-133. · Zbl 0473.68043 |

[13] | J. Feigenbaum and L. Fortnow, On the random-self-reducibility of complete sets,University of Chicago Technical Report 90-22, 1990. · Zbl 0789.68057 |

[14] | S. Fenner, L. Fortnow, and S. Kurtz, Gap-definable counting classes,University of Chicago Technical Report 90-32, 1990. · Zbl 0802.68051 |

[15] | M. Garey and D. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Co., 1979 · Zbl 0411.68039 |

[16] | S. Goldwasser, S. Micali, andC. Rackoff, The knowledge complexity of interactive proofs,SIAM J. Comput. 18 (1989), 186-208. (Preliminary version appeared inProc. 18th Ann. ACM Symp. Theory of Computing, 1985, 291-304.) · Zbl 0677.68062 |

[17] | S. Goldwasser and M. Sipser, Private coins versus public coins in interactive proof systems, inRandomness in Computation, S. Micali, ed.,Advances in Computing Research 5, JAI Press, 1989, 73-90. |

[18] | O. Goldreich, S. Micali, and A. Wigderson, Proofs that yield nothing but their validity and a methodology of cryptographic protocol design, inProc. 27th Ann. IEEE Symp. Foundations of Comp. Sci., 1986, 174-187. |

[19] | R. Lipton, New directions in testing, inProceedings of the DIMACS Workshop on Distributed Computing and Cryptography, 1989, to appear. |

[20] | C. Lund, L. Fortnow, H. Karloff, and N. Nisan, Algebraic methods for interactive proof systems, inProc. 31st Ann. IEEE Symp. Foundations of Comp. Sci.,1990, 1-10. |

[21] | A. A. Razborov, Lower bounds for the size of circuits of bounded depth with a complete basis including the logical addition function (in Russian),Matem. Zametki 41 (1981), 598-607. (English translation inMath. Notes of the Acad. Sci. USSR 41:4, 333-338.) |

[22] | U. Schöning, Probabilistic complexity classes and lowness, inProc. 2nd Ann. IEEE Structure in Complexity Theory Conf., 1987, 2-8. |

[23] | A. Shamir, IP=PSPACE, inProc. 31st Ann. IEEE Symp. Foundations of Comp. Sci., 1990, 11-15. |

[24] | R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, inProc. 19th Ann. ACM Symp. Theory of Computing, 1987, 77-82. |

[25] | L. Stockmeyer, The Polynomial-time hierarchy,Theoretical Computer Science 3 (1977), 1-22. · Zbl 0353.02024 |

[26] | S. Toda, On the computational powel of PP and ?P, inProc. 30th Ann. IEEE Symp. Foundations of Comp. Sci, 1989, 514-519. |

[27] | L. Valiant, The complexity of computing the permanent,Theoretical Computer Science 8 (1979), 189-201. · Zbl 0415.68008 |

[28] | L. Valiant andV. Vazirani, NP is as easy as detecting unique solutions,Theoretical Computer Science 47 (1986), 85-93. · Zbl 0621.68030 |

[29] | H. Venkateswaran, Circuit definitions of nondeterministic complexity classes, inProc. 8th FST & TCS, Lecture Notes in Comp. Sci 338 (1988), 175-192. · Zbl 0666.68046 |

[30] | V. Zankó, #P-completeness via many-one reductions,Internat. J. of Foundat. Comp. Sci., to appear · Zbl 0739.68036 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.