<p>You may be interested in the topic of <a href="https://en.wikipedia.org/wiki/Holographic_algorithm" rel="nofollow noreferrer">Holographic Algorithms</a>, which has been developed over the last decade. In <a href="https://ac.els-cdn.com/S0022000010000899/1-s2.0-S0022000010000899-main.pdf?_tid=fc52545a-fe12-4dac-a042-def5fc37b35c&amp;acdnat=1523021706_ceda8e7e8581a8b934f33fcfd2e8cc87" rel="nofollow noreferrer">this paper</a> Cai and Lu give families of counting problems which are <strong>#P</strong>-hard in general, but in <strong>P</strong> modulo certain Mersenne primes. This line of research lead to several <strong>P</strong> vs. <strong>#P</strong> dichotomy results classifying what families of constraints lead to easy/hard counting problems.</p>

CC BY-SA 3.0
2018-04-06T13:39:56.880Z
2018-04-06T13:39:56.880Z
Martin Schwarz
<p>We know that bipartite planar perfect matching count is easy, permanent mod $3^t$ is easy for orthogonal matrices, permanent mod $2$ is easy, bounded rank permanent is easy. </p>

<p>Outside of permanent which other hard counting problems have special cases that are easy? One example is counting points in polytope in fixed dimension.</p>

CC BY-SA 3.0
2018-04-05T08:20:48.160Z
Your question looks a bit broad to me. First you talk about counting modulo, so are you interested in this kind of counting problems or exact counting? Which area? #SAT is easy on some structured instances. So is #VertexCover. How do you even define counting problem (like permanent is not really a counting problem even if we can define it this way)? Function in #P? But then every function in FP is easy...
holf
CC BY-SA 3.0
2018-04-05T10:08:26.713Z
I changed the wording. I am interested in both counting modulo and exact counting.
Turbo
<counting-complexity><big-list>
Special cases of hard counting problems that are easy
Turbo
# Special cases of hard counting problems that are easy

(Asked by: username_0 on 2018-04-05)

We know that bipartite planar perfect matching count is easy, permanent mod $3^t$ is easy for orthogonal matrices, permanent mod $2$ is easy, bounded rank permanent is easy.

Outside of permanent which other hard counting problems have special cases that are easy? One example is counting points in polytope in fixed dimension.

**Tags:** counting-complexity, big-list
> **Comments:**
> **username_1**: Your question looks a bit broad to me. First you talk about counting modulo, so are you interested in this kind of counting problems or exact counting? Which area? #SAT is easy on some structured instances. So is #VertexCover. How do you even define counting problem (like permanent is not really a counting problem even if we can define it this way)? Function in #P? But then every function in FP is easy...  
> **username_0**: I changed the wording. I am interested in both counting modulo and exact counting.  

---

## 1 answers

### Answer by username_2 on 2018-04-06. Score: 2

You may be interested in the topic of [Holographic Algorithms](https://en.wikipedia.org/wiki/Holographic_algorithm), which has been developed over the last decade. In [this paper](https://ac.els-cdn.com/S0022000010000899/1-s2.0-S0022000010000899-main.pdf?_tid=fc52545a-fe12-4dac-a042-def5fc37b35c&acdnat=1523021706_ceda8e7e8581a8b934f33fcfd2e8cc87) Cai and Lu give families of counting problems which are **#P**-hard in general, but in **P** modulo certain Mersenne primes. This line of research lead to several **P** vs. **#P** dichotomy results classifying what families of constraints lead to easy/hard counting problems.


---

