DocumentCode :
3152026
Title :
Formal power series: an algebraic approach to the GapP and #P functions
Author :
Li, Lide
Author_Institution :
Dept. of Comput. Sci., Chicago Univ., IL, USA
fYear :
1992
fDate :
22-25 Jun 1992
Firstpage :
144
Lastpage :
154
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Structure in Complexity Theory Conference, 1992., Proceedings of the Seventh Annual
Conference_Location :
Boston, MA
Print_ISBN :
0-8186-2955-X
Type :
conf
DOI :
10.1109/SCT.1992.215390
Filename :
215390
Link To Document :
بازگشت