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?


3 Answers 3


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$.

  • $\begingroup$ Thank you for your answer! It's great to hear from someone who was there. Those references look very helpful, thank you. $\endgroup$
    – Elle Najt
    Commented Jan 30, 2019 at 20:51

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


The census functions of unambiguous context-free languages can be computed in polynomial time. However, there exist context-free languages whose census functions are #P1-complete. We also have that there exist deterministic one-counter two-way automata, and there exist nondeterministic one-way one-counter automata whose census functions are #P1-complete.

  • 3
    $\begingroup$ Add citations for these results? $\endgroup$
    – Neal Young
    Commented Apr 24 at 22:05

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.