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

CC BY-SA 3.0
2013-05-29T17:40:47.603Z
[Schöning theorem](http://dx.doi.org/10.1016/0304-3975%2882%2990114-1): [here](http://cstheory.stackexchange.com/a/8046/) and [here](http://cstheory.stackexchange.com/a/7640).
Kaveh
CC BY-SA 3.0
2013-05-29T23:30:42.920Z
@Kaveh Oh, great.  Thanks Kaveh.  I incorporated your linked info into my answer.
Tyson Williams
CC BY-SA 3.0
2013-05-30T01:04:13.757Z
Are oracle classes obviously c.e.?
 Schöning's result relies on both the classes being c.e.
András Salamon
CC BY-SA 3.0
2013-05-30T02:08:16.017Z
@András, it requires the languages in the classes to be decidable and in addition we should be able to computably enumerate the languages inside them. I guess you are concerned with the second one. If two classes are computably presentable then their oracle class is also: just enumerate their product.
Kaveh
CC BY-SA 3.0
2013-05-29T16:36:23.720Z
2013-05-29T23:27:29.940Z
2013-05-29T23:27:29.940Z
Tyson Williams
<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>

<cc.complexity-theory><reference-request><complexity-classes><counting-complexity><conditional-results>
Intermediate Problems between FP and #P
dean
# Intermediate Problems between FP and #P

(Asked by: username_0 on 2013-05-29)

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.

**Tags:** cc.complexity-theory, reference-request, complexity-classes, counting-complexity, conditional-results

---

## 1 answers

### Answer by username_1 on 2013-05-29. Score: 5

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

> **Comments:**
> **username_2**: [Schöning theorem](http://dx.doi.org/10.1016/0304-3975%2882%2990114-1): [here](http://cstheory.stackexchange.com/a/8046/) and [here](http://cstheory.stackexchange.com/a/7640).  
> **username_1**: @Kaveh Oh, great.  Thanks Kaveh.  I incorporated your linked info into my answer.  
> **username_3**: Are oracle classes obviously c.e.?  Schöning's result relies on both the classes being c.e.  
> **username_2**: @András, it requires the languages in the classes to be decidable and in addition we should be able to computably enumerate the languages inside them. I guess you are concerned with the second one. If two classes are computably presentable then their oracle class is also: just enumerate their product.  

---

