%0 Journal Article %1 dyer04 %A Dyer, Martin %A Goldberg, Leslie Ann %A Greenhill, Catherine %A Jerrum, Mark %D 2004 %J Algorithmica %K approximation complexity counting %N 3 %P 471--500 %T The Relative Complexity of Approximate Counting Problems %U http://dx.doi.org/10.1007/s00453-003-1073-y %V 38 %X 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.

@article{dyer04, 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.}, added-at = {2009-05-18T19:18:38.000+0200}, author = {Dyer, Martin and Goldberg, Leslie Ann and Greenhill, Catherine and Jerrum, Mark}, biburl = {https://www.bibsonomy.org/bibtex/226cf6f742b09dd2bb934c31f70470420/mboley}, description = {SpringerLink - Zeitschriftenbeitrag}, interhash = {a0d609804f10204fcb3cac646e6165c9}, intrahash = {26cf6f742b09dd2bb934c31f70470420}, journal = {Algorithmica}, keywords = {approximation complexity counting}, month = mar, number = 3, pages = {471--500}, timestamp = {2009-05-18T19:18:38.000+0200}, title = {The Relative Complexity of Approximate Counting Problems}, url = {http://dx.doi.org/10.1007/s00453-003-1073-y}, volume = 38, year = 2004 }