Title :
A characterization of #P by arithmetic straight line programs
Author :
Babai, László ; Fortnow, Lance
Author_Institution :
Chicago Univ., IL, USA
Abstract :
#P functions are characterized by certain straight-line programs of multivariate polynomials. The power of this characterization is illustrated by a number of consequences. These include a somewhat simplified proof of S. Toda´s (1989) theorem that PH⊆P#P, as well as an infinite class of potentially inequivalent checkable functions
Keywords :
computational complexity; polynomials; programming theory; #P functions; arithmetic straight line programs; inequivalent checkable functions; infinite class; multivariate polynomials; Arithmetic; Computer aided instruction; Input variables; Polynomials; Wire;
Conference_Titel :
Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on
Conference_Location :
St. Louis, MO
Print_ISBN :
0-8186-2082-X
DOI :
10.1109/FSCS.1990.89521
