6
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 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$ – Samuel Schlesinger Mar 16 '17 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$ – Emil Jeřábek Mar 16 '17 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$ – Jonas Kölker Mar 16 '17 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$ – Jan Johannsen Mar 17 '17 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$ – Jonas Kölker Mar 19 '17 at 12:45
4
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

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.