Concrete examples of $\sharp P_1$ complete problems? Self avoiding walks?

Question

The only examples of $\sharp P_1$ complete problems I've seen are fairly abstract : e.g. here https://www.math.cmu.edu/~af1p/Teaching/MCC17/Papers/enumerate.pdf

Valiant proves that there exists a $\sharp P_1$ complete sub-pattern matching type-problem, but he doesn't give it explicitly.

I know it was conjectured ( for example, it's mentioned here: https://www.sciencedirect.com/science/article/pii/S030439750300080X ) that the number of self avoiding walks of length $n$ might be a $\sharp P_1$ complete problem. Has there been any progress on this problem? Or are there similar counting problems (some explicit combinatorial family) which have been shown to be $\sharp P_1$ complete?

Answer 1

As someone with a long time interest in this complexity class, I don't believe there has been any significant work on $\#P_1$ since. (I was a Ph.D. student of Mitsu Ogihara, the second author of the paper you cite, and actually raised - in informal discussions with Mitsu - the open question you cite; of course, all the actual results on this problem are due to Mitsu and his coauthors only, I did not contribute to any of them)

What is known is that $\#P_1$ is a rather weak class: whereas (by Toda's theorem) $\#P$ is hard for the polynomial hierarchy, the assumption $\#P_1 = FP$ has substantially weaker implications (P=BPP). This is another result due to Mitsu.

There are interesting complexity questions in enumerative combinatorics. But (naturally as it may be) no connection seems to have been made yet to the class $\#P_1$.

Answer 2

Here is another $\mathsf{\#P_1}$-complete problem from logic that you might find interesting:

Paul Beame, Guy Van den Broeck, Eric Gribkoff, Dan Suciu: Symmetric Weighted First-Order Model Counting. PODS 2015: 313-328 https://arxiv.org/pdf/1412.1505.pdf