<p>Assuming $\mathsf{PH}$ does not collapse and that Graph Isomorphism is not in $\mathsf{P}$, then $\# GI$ (the counting version of graph isomorphism) satisfies your conditions. This is because $\# GI \equiv_m^p GI$.</p>

CC BY-SA 4.0
2020-08-24T16:29:26.063Z
I have a simple clarification. If $P=NP$ then is $\#GI$ is $\#P$-complete?
Turbo
CC BY-SA 4.0
2020-08-24T18:45:55.363Z
Unknown. If that were true, then we would have P=NP implies $FP = \# P$ (since $\# GI$ is equivalent to GI), but the latter implication is not known.
Joshua Grochow
CC BY-SA 3.0
2014-07-31T12:57:21.213Z
2014-07-31T12:57:21.213Z
Joshua Grochow
<h1><a href="https://cstheory.stackexchange.com/q/17824/17082">The previous question</a></h1>

<p>Do there exist intermediate problems (in the sense of Ladner's Theorem) for FP vs. #P? I assume that something is known, because I read some papers concerned with FP/#P dichotomies. However, I couldn't find a reference.</p>

<h1><a href="https://cstheory.stackexchange.com/a/17827/17082">An Answer to the previous question</a></h1>

<p>Use Schöning's theorem:</p>

<blockquote>
  <p>Let $A_1$, $A_2$ be recursive sets and $C_1$, $C_2$ be classes of recursive sets with the following properties:</p>
  
  <ol>
  <li>$A_1 \notin C_1$, $A_2 \notin C_2$</li>
  <li>$C_1$ and $C_2$ are recursively presentable, </li>
  <li>$C_1$ and $C_2$ are closed under finite variations. </li>
  </ol>
  
  <p>Then there exists a recursive set $A$ such that:</p>
  
  <ol>
  <li>$A \notin C_1$, $A \notin C_2$, </li>
  <li>if $A_1 \in \mathsf{P}$ and $A_2\notin \{ \emptyset, \Sigma^* \}$, then $A \leq^{\mathsf{P}}_m A_2$. </li>
  </ol>
</blockquote>

<p>For the purposes of counting dichotomy theorems, the two relevant classes of decision problems are $\text{P}$ and $\text{P}^{\#\text{P}}$.</p>

<h1>My question</h1>

<blockquote>
  <p>Is there a concrete example of #P intermediate problem under some plausible assumption?
  More specifically, is there an <em>explicit</em> function $F$ satisfying the following conditions?
  $F\notin \mathsf{FP}$ and $F$ is <em>not</em>  $\# \mathsf{P}$-complete.</p>
</blockquote>

CC BY-SA 3.0
2014-07-31T12:08:36.163Z
For P vs. $\mathrm{P^{\#P}}$, just take SAT, or any other problem in the polynomial hierarchy assumed not to be in P.
Emil Jeřábek
<cc.complexity-theory><complexity-classes><counting-complexity>
Example of #P-intermediate problem
souter
# Example of #P-intermediate problem

(Asked by: username_0 on 2014-07-31)

# [The previous question](https://cstheory.stackexchange.com/q/17824/17082)

Do there exist intermediate problems (in the sense of Ladner's Theorem) for FP vs. #P? I assume that something is known, because I read some papers concerned with FP/#P dichotomies. However, I couldn't find a reference.

# [An Answer to the previous question](https://cstheory.stackexchange.com/a/17827/17082)

Use Schöning's theorem:

> Let $A\_1$, $A\_2$ be recursive sets and $C\_1$, $C\_2$ be classes of recursive sets with the following properties:
>
> 1. $A\_1 \notin C\_1$, $A\_2 \notin C\_2$
> 2. $C\_1$ and $C\_2$ are recursively presentable,
> 3. $C\_1$ and $C\_2$ are closed under finite variations.
>
> Then there exists a recursive set $A$ such that:
>
> 1. $A \notin C\_1$, $A \notin C\_2$,
> 2. if $A\_1 \in \mathsf{P}$ and $A\_2\notin \{ \emptyset, \Sigma^\* \}$, then $A \leq^{\mathsf{P}}\_m A\_2$.

For the purposes of counting dichotomy theorems, the two relevant classes of decision problems are $\text{P}$ and $\text{P}^{\#\text{P}}$.

# My question

> Is there a concrete example of #P intermediate problem under some plausible assumption?
> More specifically, is there an *explicit* function $F$ satisfying the following conditions?
> $F\notin \mathsf{FP}$ and $F$ is *not* $\# \mathsf{P}$-complete.

**Tags:** cc.complexity-theory, complexity-classes, counting-complexity

> **Comments:**
> **username_1**: For P vs. $\mathrm{P^{\#P}}$, just take SAT, or any other problem in the polynomial hierarchy assumed not to be in P.  

---

## 1 answers

### Answer by username_2 on 2014-07-31. Score: 17

Assuming $\mathsf{PH}$ does not collapse and that Graph Isomorphism is not in $\mathsf{P}$, then $\# GI$ (the counting version of graph isomorphism) satisfies your conditions. This is because $\# GI \equiv\_m^p GI$.

> **Comments:**
> **username_3**: I have a simple clarification. If $P=NP$ then is $\#GI$ is $\#P$-complete?  
> **username_2**: Unknown. If that were true, then we would have P=NP implies $FP = \# P$ (since $\# GI$ is equivalent to GI), but the latter implication is not known.  

---

