# Is there a #$P$-complete counting problem such that every (valid) instance of its decision version is a Yes-instance?

I want to know whether there is a decision problem, written EasyProblem, satisfying the follow property:

• For every valid instance $$x$$, $$x$$ is a Yes-instance for EasyProblem (if we construct EasyProblem as a nature problem). Formally speaking, maybe we can define EasyProblem as a language $$L \in \mathrm{DTIME}(n)$$ or even $$L \in \mathrm{DTIME}(1)$$.

• The counting version #EasyProblem is in #$$P$$-complete.

Really what I'm asking is: can we construct a very easy decision problem, but its counting version is too hard? Or can we construct a very hard counting poblem, but its decision version is too easy?

## 1 Answer

An example of a such problem in $$\mathrm{DTIME}(n)$$ is DNF satisfiability . Its counting version is #P-complete , but its decision version can be solved by simply checking if there is a conjunction that is satisfiable.

For $$\mathrm{DTIME}(1)$$ I think the answer is that there are no such problems because we can iterate over all computation paths in $$O(1)$$ so counting is easy.

Note that in general, disallowing instances with answer 0 does not change the #P-completeness of any problem whose decision version is in P because we can check this case in polynomial time.

• If we disallow the instance with answer 0, then we can construct an algorithm that returns Yes in $O(1)$ time (since we can encode all the invalid input to as a string). How to understand the second paragraph in your answer? It make sense, but there is a contradiction. – TeamBright Dec 7 '20 at 8:23
• Yeah, that is a good point. I think the contradiction arises from non-rigorous definitions. In particular, I think the definition that there are Yes-instances, No-instances, and invalid instances is incompatible with the standard definitions of #P-completeness. For the standard definitions there are only Yes-instances and No-instances (invalid instances are No-instances). – Laakeri Dec 7 '20 at 8:38
• Let me give an example, suppose that $L = \{ y \vee \varphi \mid \varphi \text{ is a DNF with varibles } x_{1}, x_{2}, \ldots, x_{n} \}$. Since #DNF is #$\mathrm{P}$-complete, so is $L$. But $L \in \mathrm{DTIME}(1)$ right? Otherwise, there is not a $\mathrm{DTIME}(1)$ language anymore. – TeamBright Dec 7 '20 at 11:45
• You need to use at least $\Theta(n)$ computation to check if the input is a valid representation of DNF (note that inputs are binary strings, not arbitrary data). Yeah I guess there is not many interesting languages in DTIME(1). – Laakeri Dec 7 '20 at 12:22
• I think I have got the answer that I want. That is there do exist a decision problem in $\mathrm{DTIME}(1)$, but the counting version is complete in #$\mathrm{P}$. (Thanks to your answer,) $L = \{ y \vee \varphi \mid \varphi \text{ is a DNF with variables }x_{1}, x_{2}, \ldots, x_{n} \}$. – TeamBright Dec 10 '20 at 7:03