# What is the complexity class of counting Yes/No instances of an NP problem?

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?

• 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.
– D.W.
Commented Dec 10, 2022 at 17:25

I think you are looking for $$\#\mathsf{P}$$, a set of counting problems.
See this paper for some examples of $$\#\mathsf{P}$$-complete problems.
• 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. Commented Dec 10, 2022 at 13:27