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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.