The Complexity of Counting Functions with Easy Decision Version

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

.

We study these problems in respect to the complexity class

TotP

, which contains functions that count the number of

all

paths of a PNTM. We first compare

TotP

to

#P

and

#PE

and show that

FP

⊆

TotP

⊆

#PE

⊆

#P

and that the inclusions are proper unless

P = NP

.

We then show that several natural

#PE

problems — including the ones mentioned above — belong to

TotP

. Moreover, we prove that

TotP

is exactly the Karp closure of self-reducible functions of

#PE

. Therefore, all these problems share a remarkable structural property: for each of them there exists a polynomial-time nondeterministic Turing machine which has as many computation paths as the output value.