<%@ page language="java" contentType="text/html" %>
<%-- Include common initialisation code --%>
<%@ include file="/arch/common.jsp" %>
<%-- The current tab --%>
<% String currentTab = "Research"; %>
<%-- Content of navigation pane --%>
<%@ include file="nav.jsp" %>
<% showCurrentLink=true; %>
<%-- Current navigation location --%>
<% String currentNav = "Reports and Theses"; %>
<%-- Include the code for the document header --%>
<%@ include file="/arch/header.jsp" %>
Research Report CS-RR-370
<%-- Include the code for the lines and navigation --%>
<%@ include file="/arch/middle.jsp" %>
Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill and Mark Jerrum,
On the Relative Complexity of Approximate Counting Problems
(February 20, 2000).
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.
Download
cs-rr-370.ps.gz
<%-- Include the code for the document footer --%>
<%@ include file="/arch/footer.jsp" %>