Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

On the relative complexity of approximate counting problems

Tools
- Tools
+ Tools

Dyer, Martin, Goldberg, Leslie Ann, Greenhill, Catherine and Jerrum, Mark (2000) On the relative complexity of approximate counting problems. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

[img]
Preview
PDF (Department of Computer Science Research Report)
WRAP_cs-rr-370.pdf - Other - Requires a PDF viewer.

Download (463Kb) | Preview

Request Changes to record.

Abstract

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: Report
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH): Counting, Computational complexity
Series Name: Department of Computer Science research report
Publisher: University of Warwick. Department of Computer Science
Official Date: 28 February 2000
Dates:
DateEvent
28 February 2000Completion
Number: Number 370
Number of Pages: 30
DOI: CS-RR-370
Institution: University of Warwick
Theses Department: Department of Computer Science
Status: Not Peer Reviewed
Publication Status: Unpublished
Funder: Engineering and Physical Sciences Research Council (EPSRC), European Strategic Programme of Research and Development in Information Technology (ESPRIT), Leverhulme Trust (LT)
Related URLs:
  • Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us