1
$\begingroup$

Let's say that I have an NP-complete problem such as the Clique Problem. Let's also assume that I have a finte set of graphs. What is the complexity of counting Yes/No instances?

More specifically let's define a new decision problem that returns Yes on a finite set of graphs if the number of Yes instances is $\geq$ a constant $k$ and the number of No instances is $\leq$ a constant $l$ Equivalently $l' \leq \operatorname{count}(Yes) \leq k$. In what complexity class does this problem belong? I know it can be solved in polynomial time with an NP oracle but is it hard in this class or is there a lower bound?

In a more general setting if I need the set of graphs to satisfy a condition $c(\operatorname{count}(Yes), \operatorname{count}(No)) \leq k$, where $c$ is an arbitrary function, does the problem become harder?

Improve this question
$\endgroup$
1
  • $\begingroup$ Please edit your question to specify the problem more carefully. What are the inputs to the algorithm? Are $l,k$ inputs? Are they fixed numbers like 3,5 and you're allowed to choose a different algorithm for every choice of $l,k$? Something else? It might help to describe the context in which you encountered this or the motivation for asking. $\endgroup$
    – D.W. ♦
    Commented Dec 10, 2022 at 17:25

1 Answer 1

Reset to default
2
$\begingroup$

I think you are looking for $\#\mathsf{P}$, a set of counting problems.

See this paper for some examples of $\#\mathsf{P}$-complete problems.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I think $\# P$ might be harder since I don't care about the exact number of Yes instances, only bounds on it. E.g. if I only have a bound on Yes instances I can verify in polynomial time that there are at least that many. $\endgroup$
    – thiaamak
    Commented Dec 10, 2022 at 13:27
  • 2
    $\begingroup$ If you can count the exact number, you can deduce bounds. Conversely, if you can know bounds, you can find the exact number using dichotomic search. So I think those class are equals. $\endgroup$
    – Nathaniel
    Commented Dec 10, 2022 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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