The relative complexity of approximate counting problems
Dyer, Martin, Goldberg, Leslie Ann, Greenhill, Catherine and Jerrum, Mark. (2004) The relative complexity of approximate counting problems. Algorithmica, Volume 38 (Number 3). pp. 471-500. ISSN 0178-4617Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/s00453-003-1073-y
Two natural classes of counting problems that are interreducible under approximation-preserving reductions are: (i) those that admit a particular kind of efficient approximation algorithm known as an "FPRAS", and (ii) those that are complete for #P with respect to approximation-preserving reducibility. We describe and investigate not only these two classes but also a 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 in a logically defined subclass of #P.
|Item Type:||Journal Article|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Q Science > QA Mathematics
|Divisions:||Faculty of Science > Computer Science|
|Journal or Publication Title:||Algorithmica|
|Official Date:||10 March 2004|
|Number of Pages:||30|
|Page Range:||pp. 471-500|
|Access rights to Published version:||Restricted or Subscription Access|
|Conference Paper Type:||Paper|
|Type of Event:||Workshop|
Actions (login required)