<p>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.</p>

CC BY-SA 3.0
2017-03-16T10:29:42.493Z
2017-03-16T10:29:42.493Z
Jonas Kölker
<p>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).</p>

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

<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?</p>

CC BY-SA 3.0
2017-03-16T08:07:21.967Z
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
CC BY-SA 3.0
2017-03-16T08:53:19.433Z
(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
CC BY-SA 3.0
2017-03-16T10:18:39.243Z
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
CC BY-SA 3.0
2017-03-17T08:48:07.207Z
Can you please add or at least link to a definition of the class ASP and the used notion of completeness.
Jan Johannsen
CC BY-SA 3.0
2017-03-19T12:45:29.320Z
http://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
CC BY-SA 3.0
2017-03-20T15:28:37.217Z
The original source of ASP seems to be http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.5277 Ueda and Nagao 1996.
András Salamon
<cc.complexity-theory><complexity-classes><counting-complexity><unique-solution>
What's the relationship between ASP-complete and #P-complete?
Jonas Kölker
# What's the relationship between ASP-complete and #P-complete?

(Asked by: username_0 on 2017-03-16)

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?

**Tags:** cc.complexity-theory, complexity-classes, counting-complexity, unique-solution

> **Comments:**
> **username_1**: 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.  
> **username_2**: (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.  
> **username_0**: 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?  
> **username_3**: Can you please add or at least link to a definition of the class ASP and the used notion of completeness.  
> **username_0**: http://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).  
> **username_4**: The original source of ASP seems to be http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.5277 Ueda and Nagao 1996.  

---

## 1 answers

### Answer by username_0 on 2017-03-16. Score: 4 | Accepted answer

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.


---

