Abstract
Abstract Two natural classes of counting problems that are interreducible
under approximation-preserving reductions are: (i) those thatadmit a particular kind of efficient approximation algorithmknown as an “FPRAS”,and (ii) those that are complete for #Pwith respect to approximation-preserving reducibility.We describe and investigate not only these two classes but alsoa third class, of intermediate complexity,that is not known to be identical to (i) or (ii).The third class can be characterised as the hardest problems ina logically defined subclass of #P.
Users
Please
log in to take part in the discussion (add own reviews or comments).