Browse Prior Art Database

Exact Counting is as Easy as Approximate Counting

IP.com Disclosure Number: IPCOM000148379D
Original Publication Date: 1986-Jun-30
Included in the Prior Art Database: 2007-Mar-29

Publishing Venue

Software Patent Institute

Related People

Cai, Jin-yi: AUTHOR [+3]

Abstract

Jin-yi Cai t Lane A. Hemachandra$ Department of Computer Science Cornell UniversityIthaca, NY 14853 ?' Research supported by a Sage Fellowship and NSF grant DCR-8301766. $: Research supported by a Fannie and John Hertz Foundation Fellowship and NSF grant DCR- 8301766. Exact Counting is as Easy as Approximate Counting Jin-yi Cai' Lane A. Henaachandrat Department of Computer Science Cornell University It haca, NY 14853 Abstract We show that exact counting and approximate counting are polynomially equivalent. That is,p#P p Approx#]P where #P is a function that computes the number of solutions to a given Boolean formula f (denoted by )If I I , and Approx#P computes a short list that contains 11 f 11. It follows that if there is a good polynomial time approximator for #P (i.e., one where the list has at most O((jI1-') elements), then P NP P#' and probabilistic polynomial time equals polynomial time. Thus we have strong evidence that #P can not be easily approximated.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 17% of the total text.

Page 1 of 14

Exact Counting is as Easy as Approximate Counting

Jin-yi Cai t

Lane A. Hemachandra$

Department of Computer Science Cornell University
Ithaca, NY 14853

?' Research supported by a Sage Fellowship and NSF grant DCR-8301766.

$: Research supported by a Fannie and John Hertz Foundation Fellowship and NSF grant DCR-

8301766.

[This page contains 1 picture or other non-text object]

Page 2 of 14

[This page contains 1 picture or other non-text object]

Page 3 of 14

Exact Counting is as Easy as Approximate Counting

Jin-yi Cai' Lane A. Henaachandrat

Department of Computer Science

Cornell University

It haca, NY 14853

Abstract

  We show that exact counting and approximate counting are polynomially equivalent. That is,
p#P = p Approx#]P

where #P is a function that computes the number of solutions to a given Boolean formula f (denoted by )If I I ) , and Approx#P computes a short list that contains 11 f 11.

It follows that if there is a good polynomial time approximator for #P
(i.e., one where the list has at most O((jI1-') elements), then P = NP = P#' and probabilistic polynomial time equals polynomial time. Thus we have strong evidence that #P can not be easily approximated.

1 Prelude

Suppose a demon comes into your office and says, "I have here a polynomial time ma- chine. Give it a Boolean formula and it will print the number of satisfying assignments the formula has." Enraged, you reply, "Your claim implies P=NP, false and foul fiend. Return to your infernal home.' Her deception discovered, the embarrassed demon (who knows that P # NP) leaves you in a cloud of smoke.

  However, she returns the next day and says, 'I got the last bug out of that polynomial time machine. Give it a formula and it will now print out a short list of numbers, one of

'Research supported by a Sage Fellowship and NSF grant DCR-8301766.
+Research supported by a Fannie and John Hertz Foundation Fellowship and NSF grant DCR-8301766.

[This page contains 1 picture or other non-text object]

Page 4 of 14

which is the number of satisfying assignments the formula has." You are intrigued. Just what is this demon offering? You suddenly remember reading this paper. Without the slightest hesitation you reply, "Your claim still implies P=MP, dishonest demon. Return to the abyss, and trouble me no more." Your soul secure, you return to the search for a proof that P # NP.

2 Introduction

#P is the class of functions that count the accepting paths of some NP machine [Vd79b].

These functions can count the number of cliques of a given size, compute the per- manent of a matrix and solve many other interesting counting versions of NP prob- lems [Val7Yb,Val79a]. P # ~
is the class of languages computable by polynomial time machines endowed with the power of counting.

  #P questions seem hard. Though they can be answered by brute force in PSPACE, it is not known if they are in the po...