0
$\begingroup$

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?

Improve this question
$\endgroup$
1
$\begingroup$

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.

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.

[1] https://en.m.wikipedia.org/wiki/Disjunctive_normal_form

[2] https://en.m.wikipedia.org/wiki/%E2%99%AFP-complete

Improve this answer
$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$ – TeamBright Dec 7 '20 at 8:23
  • $\begingroup$ 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). $\endgroup$ – Laakeri Dec 7 '20 at 8:38
  • $\begingroup$ 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. $\endgroup$ – TeamBright Dec 7 '20 at 11:45
  • $\begingroup$ 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). $\endgroup$ – Laakeri Dec 7 '20 at 12:22
  • $\begingroup$ 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} \}$. $\endgroup$ – TeamBright Dec 10 '20 at 7:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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