4

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?

David E Speyer
  • 401
  • 2
  • 10
  • 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 Sep 26 '13 at 19:09
  • 3
    @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 Sep 26 '13 at 19:16
  • Right, and "a lot of room between pretty hard and #P-complete" would depend on your "reasonable conjectures." – Yoshio Okamoto Sep 26 '13 at 19:22
  • 2
    @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 Sep 26 '13 at 20:00
  • 4
    @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 Sep 26 '13 at 20:41
  • 1
    @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 Sep 26 '13 at 21:05
  • 1
    @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 Sep 26 '13 at 21:39
  • @DavidRicherby Thanks! I wasn't thinking clearly on that point; it is a duplicate then. – David E Speyer Sep 26 '13 at 21:41

0 Answers0