<p>Look here: "<a href="https://link.springer.com/chapter/10.1007%2F11821069_64" rel="noreferrer">The Complexity of Counting Functions with Easy Decision Version</a>"</p>

<p>by Zachos and Pagourtzis. </p>

<blockquote>
  <p>We investigate the complexity of counting problems that belong to the complexity class #P and have an easy decision version. These problems constitute the class #PE which has some well-known representatives such as #Perfect Matchings, #DNF-Sat, and NonNegative Permanent. An important property of these problems is that they are all #P-complete, in the Cook sense, while they cannot be #P-complete in the Karp sense unless P = NP.</p>
</blockquote>

CC BY-SA 3.0
2017-05-20T10:54:30.880Z
2017-05-20T10:54:30.880Z
PsySp
<p>We know that an NP complete problem with a parsimonious reduction but a many one reduction is candidate problem for NP complete problem not being #P hard.</p>

<ol>
<li>Likewise is there a possible classification of which P-complete or NL-complete or in general P problems are likely to have counting problems #P-hard and not in #P-hard?</li>
</ol>

<counting-complexity>
#P-complete with decision P
Turbo
# #P-complete with decision P

(Asked by: username_0 on 2017-05-20)

We know that an NP complete problem with a parsimonious reduction but a many one reduction is candidate problem for NP complete problem not being #P hard.

1. Likewise is there a possible classification of which P-complete or NL-complete or in general P problems are likely to have counting problems #P-hard and not in #P-hard?

**Tags:** counting-complexity

---

## 1 answers

### Answer by username_1 on 2017-05-20. Score: 5

Look here: "[The Complexity of Counting Functions with Easy Decision Version](https://link.springer.com/chapter/10.1007%2F11821069_64)"

by Zachos and Pagourtzis.

> We investigate the complexity of counting problems that belong to the complexity class #P and have an easy decision version. These problems constitute the class #PE which has some well-known representatives such as #Perfect Matchings, #DNF-Sat, and NonNegative Permanent. An important property of these problems is that they are all #P-complete, in the Cook sense, while they cannot be #P-complete in the Karp sense unless P = NP.


---

