# What's the relationship between ASP-complete and #P-complete?

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?

• 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. – Samuel Schlesinger Mar 16 '17 at 8:07
• (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. – Emil Jeřábek Mar 16 '17 at 8:53
• 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? – Jonas Kölker Mar 16 '17 at 10:18
• Can you please add or at least link to a definition of the class ASP and the used notion of completeness. – Jan Johannsen Mar 17 '17 at 8:48
• 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). – Jonas Kölker Mar 19 '17 at 12:45