Title :
Formal power series: an algebraic approach to the GapP and #P functions
Author_Institution :
Dept. of Comput. Sci., Chicago Univ., IL, USA
Abstract :
The algebraic structure of GapP and #P functions is introduced by formalizing them as power series ring and semiring, respectively. It is proved that for every invertible GapP function g, Pg=P1g/, and for all positive integers i, Pg=P to the gi, power. Applying the Ladner theorem for functions, it is shown that Ps=P[s] for all S if and only if P=PP, where [S] is the subring generated by S. It also concluded that the class of rational series is contained in FP. Considering the group of all invertible functions, it is proved that all functions in the same coset with respect to FP are Turing equivalent, every Turing degree inside GapP except FP contains infinitely many cosets, and P≠PP if and only if the index of FP is infinite
Keywords :
Turing machines; computational complexity; #P functions; Ladner theorem; Turing degree; Turing equivalent; coset; hash P functions; invertible GapP function; invertible functions; positive integers; rational series; ring power series; semiring power series; Arithmetic; Automata; Complexity theory; Computer science; Polynomials; Power generation;
Conference_Titel :
Structure in Complexity Theory Conference, 1992., Proceedings of the Seventh Annual
Conference_Location :
Boston, MA
Print_ISBN :
0-8186-2955-X
DOI :
10.1109/SCT.1992.215390