-1
$\begingroup$

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?
Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

Look here: "The Complexity of Counting Functions with Easy Decision Version"

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.

Improve this answer
$\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.