<p>Here is another <span class="math-container">$\mathsf{\#P_1}$</span>-complete problem from logic that you might find interesting: </p>

<p>Paul Beame, Guy Van den Broeck, Eric Gribkoff, Dan Suciu:
Symmetric Weighted First-Order Model Counting. PODS 2015: 313-328
<a href="https://arxiv.org/pdf/1412.1505.pdf" rel="noreferrer">https://arxiv.org/pdf/1412.1505.pdf</a></p>

CC BY-SA 4.0
2019-01-31T20:30:12.653Z
2019-01-31T20:30:12.653Z
smengel
<p>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.</p>

CC BY-SA 4.0
2024-04-24T22:05:55.653Z
Add citations for these results?
Neal Young
CC BY-SA 4.0
2024-04-24T21:54:15.783Z
2024-04-24T21:54:15.783Z
user72497
<p>As someone with a long time interest in this complexity class, I don't believe there has been any significant work on <span class="math-container">$\#P_1$</span> 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 <strong>results</strong> on this problem are due to Mitsu and his coauthors only, I did not contribute to any of them)  </p>

<p>What <strong>is</strong> known is that <span class="math-container">$\#P_1$</span> is a rather weak class: whereas (by Toda's theorem) <span class="math-container">$\#P$</span> is hard for the polynomial hierarchy, the assumption <span class="math-container">$\#P_1 = FP$</span> <a href="https://arxiv.org/pdf/cs/9809002.pdf" rel="noreferrer">has substantially weaker implications</a> (P=BPP). This is another result due to Mitsu. </p>

<p>There are <a href="https://arxiv.org/pdf/1803.06636.pdf" rel="noreferrer">interesting complexity questions in enumerative combinatorics</a>. But (naturally as it may be) no connection  seems to have been made yet to the class <span class="math-container">$\#P_1$</span>.  </p>

CC BY-SA 4.0
2019-01-30T20:51:29.143Z
Thank you for your answer! It's great to hear from someone who was there. Those references look very helpful, thank you.
Elle Najt
CC BY-SA 4.0
2024-07-18T00:46:16.887Z
@GabrielIstrate Is $\oplus P_1$ known to be in $P$?
Turbo
CC BY-SA 4.0
2019-01-30T20:17:35.307Z
2019-01-30T20:17:35.307Z
Gabriel Istrate
<p>The only examples of <span class="math-container">$\sharp P_1$</span> complete problems I've seen are fairly abstract : e.g. here <a href="https://www.math.cmu.edu/~af1p/Teaching/MCC17/Papers/enumerate.pdf" rel="noreferrer">https://www.math.cmu.edu/~af1p/Teaching/MCC17/Papers/enumerate.pdf</a></p>

<p>Valiant proves that there exists a <span class="math-container">$\sharp P_1$</span> complete sub-pattern matching type-problem, but he doesn't give it explicitly.</p>

<p>I know it was conjectured ( for example, it's mentioned here: <a href="https://www.sciencedirect.com/science/article/pii/S030439750300080X" rel="noreferrer">https://www.sciencedirect.com/science/article/pii/S030439750300080X</a> ) that the number of self avoiding walks of length <span class="math-container">$n$</span> might be a <span class="math-container">$\sharp P_1$</span> 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 <span class="math-container">$\sharp P_1$</span> complete?</p>

<cc.complexity-theory><counting-complexity>
Concrete examples of $\sharp P_1$ complete problems? Self avoiding walks?
Elle Najt
# Concrete examples of $\sharp P_1$ complete problems? Self avoiding walks?

(Asked by: username_0 on 2019-01-30)

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?

**Tags:** cc.complexity-theory, counting-complexity


---

## 3 answers

### Answer by username_4 on 2019-01-30. Score: 12 | Accepted answer

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](https://arxiv.org/pdf/cs/9809002.pdf) (P=BPP). This is another result due to Mitsu.

There are [interesting complexity questions in enumerative combinatorics](https://arxiv.org/pdf/1803.06636.pdf). But (naturally as it may be) no connection seems to have been made yet to the class $\#P\_1$.

> **Comments:**
> **username_0**: Thank you for your answer! It's great to hear from someone who was there. Those references look very helpful, thank you.  
> **username_5**: @GabrielIstrate Is $\oplus P_1$ known to be in $P$?  

---

### Answer by username_1 on 2019-01-31. Score: 5

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>


---

### Answer by username_2 on 2024-04-24. Score: 0

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.

> **Comments:**
> **username_3**: Add citations for these results?  

---

