Given that ASP-reductions by definition are parsimonious and parsimonious reductions preserve #P-completeness, one might think that the counting version of all ASP-complete problems are also #P-complete (note that e.g. #3SAT is #P-complete and 3SAT is ASP-complete).

However, ASP-completeness implies that all solutions have polynomial length, whereas no such requirement is there for #P.

Is it the case that all ASP-complete problems are #P-complete? Is there some kind of relationship in the other direction as well?

  • 1
    $\begingroup$ I'm almost certain that there is a polynomial length requirement on #P, on both the individual solutions, as the internal language is in P, and the number of solutions, as there are at most exponential accepting computation paths in the running time of the machine and we can represent this in space proportional to the running time. $\endgroup$ Commented Mar 16, 2017 at 8:07
  • $\begingroup$ (1) There is a type error: ASP-complete problems are not #P-complete, their counting versions are. You gave examples yourself in the question. (2) Samuel is correct. $\endgroup$ Commented Mar 16, 2017 at 8:53
  • $\begingroup$ Wikipedia and complexity zoo agree that #P is the class of function problems of the form "compute ƒ(x)" where f is the number of accepting paths in a poly-time NTM. Given a checker M for witnesses of size p(x), I can construct one which accepts if w has length >= p(x)+1, otherwise returns M(w). It has finite accepting paths but infinitely many good witnesses, which confuses me. Is there a canonical definition of #p phrased in terms of witness checkers? $\endgroup$ Commented Mar 16, 2017 at 10:18
  • $\begingroup$ Can you please add or at least link to a definition of the class ASP and the used notion of completeness. $\endgroup$ Commented Mar 17, 2017 at 8:48
  • $\begingroup$ www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf — Given an FNP problem $X$, an instance $I$ and a solution $s$, the ASP-problem $(I, s)$ is that of finding a solution $s'$ to $I$ such that $s' \neq s$. ASP-completeness of a problem $X$ means all FNP problems reduce to $X$ via an ASP reduction (a parsimonious FNP-reduction plus a polynomial time computable bijection on solutions). $\endgroup$ Commented Mar 19, 2017 at 12:45

1 Answer 1


Let an ASP-complete problem Q be given. There is an ASP-reduction from 3SAT to Q and all ASP-reductions are parsimonious, hence it serves as a parsimonious reduction from #3SAT to #Q. Since #Q is in #P and #3SAT is #P-hard, #Q is #P-complete.


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.