Let $f_i \in FP$ and $g_i \in \#P$ for $i \in \mathbb{N}$.
It is known that: $f_1(f_2(x)) \in FP$ and that $g_1(f_1(x)) \in \#P$.
Is it known whether or not $f_1(g_1(x)) \in \#P$ or maybe $f_1(g_1(x)) \in GapP$?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ There is a classical paper about this kind of question: Mitsunori Ogiwara, Lane A. Hemachandra: A Complexity Theory for Feasible Closure Properties. J. Comput. Syst. Sci. 46(3): 295-325 (1993). For example, it considers the cases where $f_1(x)=x-1$ and $f_1(x)=x/2$. With respect to GapP, there is also: Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz: Gap-Definable Counting Classes. J. Comput. Syst. Sci. 48(1): 116-148 (1994). $\endgroup$– Thomas SJun 15, 2017 at 5:49
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
On Closure Properties of #P in the Context of PF ∘ #P
Note that FP and PF are the same complexity class. It is stated in proposition 2.1 on page 3 that FP ∘ #P = FP $^{\# P{ [1]}}$
answered Jun 17, 2017 at 3:46