3
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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

$\endgroup$
4
  • 3
    $\begingroup$ Schöning theorem: here and here. $\endgroup$
    – Kaveh
    May 29, 2013 at 17:40
  • $\begingroup$ @Kaveh Oh, great. Thanks Kaveh. I incorporated your linked info into my answer. $\endgroup$ May 29, 2013 at 23:30
  • $\begingroup$ Are oracle classes obviously c.e.? Schöning's result relies on both the classes being c.e. $\endgroup$ May 30, 2013 at 1:04
  • $\begingroup$ @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. $\endgroup$
    – Kaveh
    May 30, 2013 at 2:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.