-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – holf Apr 5 '18 at 8:20
  • $\begingroup$ I changed the wording. I am interested in both counting modulo and exact counting. $\endgroup$ – T.... Apr 5 '18 at 10:08
2
$\begingroup$

You may be interested in the topic of Holographic Algorithms, which has been developed over the last decade. In this paper 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.

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