<p><a href="http://www.sciencedirect.com/science/article/pii/S0022000096900598" rel="noreferrer">On Closure Properties of #P in the Context of PF ∘ #P</a> </p>

<hr>

<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]}}$  </p>

CC BY-SA 3.0
2017-06-17T03:46:10.903Z
2017-06-17T03:46:10.903Z
Tayfun Pay
<p>Let $f_i \in FP$ and $g_i \in \#P$ for $i \in \mathbb{N}$. <br> 
It is known that: $f_1(f_2(x)) \in FP$ and that $g_1(f_1(x)) \in \#P$. <br>
Is it known whether or not $f_1(g_1(x)) \in \#P$ or maybe $f_1(g_1(x)) \in GapP$? </p>

CC BY-SA 3.0
2017-06-15T05:49:52.940Z
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).
Thomas S
<reference-request><counting-complexity><function>
Composition of $FP$ and $\#P$ functions
Abraham Moshowitz
# Composition of $FP$ and $\#P$ functions

(Asked by: username_0 on 2017-06-14)

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$?

**Tags:** reference-request, counting-complexity, function

> **Comments:**
> **username_1**: 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).  

---

## 1 answers

### Answer by username_2 on 2017-06-17. Score: 5 | Accepted answer

[On Closure Properties of #P in the Context of PF ∘ #P](http://www.sciencedirect.com/science/article/pii/S0022000096900598)

---

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]}}$


---

