# The previous question

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

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.

• 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 Jul 31 '14 at 12:08

## 1 Answer

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