4
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ For P vs. $\mathrm{P^{\#P}}$, just take SAT, or any other problem in the polynomial hierarchy assumed not to be in P. $\endgroup$ – Emil Jeřábek Jul 31 '14 at 12:08
12
$\begingroup$

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

$\endgroup$

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.