<p>Let $R(v_{\bullet}, w_{\bullet})$ be some $P$-time computable relation between two binary strings $v_{\bullet}$ and $w_{\bullet}$. $NP$ problems are problems of the form: Given $v_{\bullet}$, determine whether there exists an $w_{\bullet}$ so that $R(v_{\bullet}, w_{\bullet})$. The $\# P$ problems are problems of the form: Given $v_{\bullet}$, count the number of $w_{\bullet}$ satisfying $R(v_{\bullet}, w_{\bullet})$.</p>

<p>There are certainly examples of $R$ from which the counting problem is hard but the existence problem is not:  Determining whether a graph has a perfect matching is in $P$, but counting the perfect matchings is $\# P$-complete.</p>

<p>What are examples of relations $R$ for the existence problem is $NP$-complete but the counting problem is, subject to reasonable conjectures, not $\# P$-complete? </p>

CC BY-SA 3.0
2013-09-26T19:09:51.397Z
If we can count the number of w's such that R(v, w) is satisfied, then we know if such a w exists or not.
Yoshio Okamoto
CC BY-SA 3.0
2013-09-26T19:16:58.497Z
@YoshioOkamoto Right. So that shows that, if the existence problem is $NP$-complete, the counting problem must be "pretty hard" (eg not in $P$). But it seems to me that there is a lot of room between "pretty hard" and $\# P$-complete. Or am I missing something?
David E Speyer
CC BY-SA 3.0
2013-09-26T19:22:28.280Z
Right, and "a lot of room between pretty hard and #P-complete" would depend on your "reasonable conjectures."
Yoshio Okamoto
CC BY-SA 3.0
2013-09-26T20:00:23.567Z
@YoshioOkamoto I intentionally left that somewhat vague. But I don't think the question is too vague to be answered. See a conversation between Timothy Chow, Lev Reyzin and Jeff Klnne at http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc about problems between $P$ and $NP$-complete, assuming various conjectures.
David E Speyer
CC BY-SA 3.0
2013-09-26T20:41:07.007Z
@DavidSpeyer: Such a problem must be NP-complete with respect to many-one reductions, but not NP-complete with respect to parsimonious reductions (=reductions that preserve the number of witnesses). Whether NPC wrt many-one is the same as NPC wrt parsimonious is a long-standing open question, and I am not even aware of any candidates that separate these notions (though I will be pleasantly surprised if someone gives an answer). But maybe you'll have more luck searching for conditional separations of parsimonious from many-one reductions.
Joshua Grochow
CC BY-SA 3.0
2013-09-26T21:05:48.740Z
@DavidRicherby Thanks! That question seems a little different  because it starts with a counting function $f: \{ 0,1 \}^{\ast} \to \mathbb{N}$ and I start with a relation $R$. If you look at the current only answer to that question, it addresses a third question of starting with a boolean function $g: \{ 0,1 \}^{\ast} \to \{ 0,1 \}$ and building a $\# P$-complete relation with $g$ as its decision problem. These three seem different to me, though certainly related.
David E Speyer
CC BY-SA 3.0
2013-09-26T21:39:04.430Z
@DavidSpeyer Defining P and #P in terms of witness relations (as you did) or functions (as in the other question) gives exactly the same classes. For example, the function definition includes all functions of the form $f(x) = |\{(x,y)\in R \text{ for some }y\}|$ where $R$ is your witness relation.
David Richerby
CC BY-SA 3.0
2013-09-26T21:41:13.857Z
@DavidRicherby Thanks! I wasn't thinking clearly on that point; it is a duplicate then.
David E Speyer
<cc.complexity-theory><counting-complexity>
What NP-complete problems are expected not to have #P-hard counting problems?
David E Speyer
# What NP-complete problems are expected not to have #P-hard counting problems?

(Asked by: username_0 on 2013-09-26)

Let $R(v\_{\bullet}, w\_{\bullet})$ be some $P$-time computable relation between two binary strings $v\_{\bullet}$ and $w\_{\bullet}$. $NP$ problems are problems of the form: Given $v\_{\bullet}$, determine whether there exists an $w\_{\bullet}$ so that $R(v\_{\bullet}, w\_{\bullet})$. The $\# P$ problems are problems of the form: Given $v\_{\bullet}$, count the number of $w\_{\bullet}$ satisfying $R(v\_{\bullet}, w\_{\bullet})$.

There are certainly examples of $R$ from which the counting problem is hard but the existence problem is not: Determining whether a graph has a perfect matching is in $P$, but counting the perfect matchings is $\# P$-complete.

What are examples of relations $R$ for the existence problem is $NP$-complete but the counting problem is, subject to reasonable conjectures, not $\# P$-complete?

**Tags:** cc.complexity-theory, counting-complexity

> **Comments:**
> **username_1**: If we can count the number of w's such that R(v, w) is satisfied, then we know if such a w exists or not.  
> **username_0**: @YoshioOkamoto Right. So that shows that, if the existence problem is $NP$-complete, the counting problem must be "pretty hard" (eg not in $P$). But it seems to me that there is a lot of room between "pretty hard" and $\# P$-complete. Or am I missing something?  
> **username_1**: Right, and "a lot of room between pretty hard and #P-complete" would depend on your "reasonable conjectures."  
> **username_0**: @YoshioOkamoto I intentionally left that somewhat vague. But I don't think the question is too vague to be answered. See a conversation between Timothy Chow, Lev Reyzin and Jeff Klnne at http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc about problems between $P$ and $NP$-complete, assuming various conjectures.  
> **username_2**: @DavidSpeyer: Such a problem must be NP-complete with respect to many-one reductions, but not NP-complete with respect to parsimonious reductions (=reductions that preserve the number of witnesses). Whether NPC wrt many-one is the same as NPC wrt parsimonious is a long-standing open question, and I am not even aware of any candidates that separate these notions (though I will be pleasantly surprised if someone gives an answer). But maybe you'll have more luck searching for conditional separations of parsimonious from many-one reductions.  
> **username_0**: @DavidRicherby Thanks! That question seems a little different  because it starts with a counting function $f: \{ 0,1 \}^{\ast} \to \mathbb{N}$ and I start with a relation $R$. If you look at the current only answer to that question, it addresses a third question of starting with a boolean function $g: \{ 0,1 \}^{\ast} \to \{ 0,1 \}$ and building a $\# P$-complete relation with $g$ as its decision problem. These three seem different to me, though certainly related.  
> **username_3**: @DavidSpeyer Defining P and #P in terms of witness relations (as you did) or functions (as in the other question) gives exactly the same classes. For example, the function definition includes all functions of the form $f(x) = |\{(x,y)\in R \text{ for some }y\}|$ where $R$ is your witness relation.  
> **username_0**: @DavidRicherby Thanks! I wasn't thinking clearly on that point; it is a duplicate then.  

---

## 0 answers

