Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

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

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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