4
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ @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? $\endgroup$
    – David E Speyer
    Commented Sep 26, 2013 at 19:16
  • 2
    $\begingroup$ @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 cstheory.stackexchange.com/questions/79/… about problems between $P$ and $NP$-complete, assuming various conjectures. $\endgroup$
    – David E Speyer
    Commented Sep 26, 2013 at 20:00
  • 4
    $\begingroup$ @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. $\endgroup$
    – Joshua Grochow
    Commented Sep 26, 2013 at 20:41
  • 1
    $\begingroup$ @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. $\endgroup$
    – David E Speyer
    Commented Sep 26, 2013 at 21:05
  • 1
    $\begingroup$ @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. $\endgroup$
    – David Richerby
    Commented Sep 26, 2013 at 21:39

0

Reset to default