7
$\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$
1
  • 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$ Jul 31, 2014 at 12:08

1 Answer 1

16
$\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$
2
  • $\begingroup$ I have a simple clarification. If $P=NP$ then is $\#GI$ is $\#P$-complete? $\endgroup$
    – Turbo
    Aug 24, 2020 at 16:29
  • $\begingroup$ Unknown. If that were true, then we would have P=NP implies $FP = \# P$ (since $\# GI$ is equivalent to GI), but the latter implication is not known. $\endgroup$ Aug 24, 2020 at 18:45

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.

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