5
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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

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

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

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