# 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?

An example of a such problem in $$\mathrm{DTIME}(n)$$ is DNF satisfiability [1]. Its counting version is #P-complete [2], 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.
• 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. Dec 7, 2020 at 8:23
• 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. Dec 7, 2020 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). Dec 7, 2020 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} \}$. Dec 10, 2020 at 7:03