fpras_bpp (504B)
1 # FPRAS BPP 2 3 [theorem]: if a [counting_problem] admits an [fpras], then the corresponding [decision_problem] of testing if the count is >0 is in [bpp] 4 - for [satisfiability_boolean] for instance: 5 - if [sharp_satisfiability] admits an [fpras], then [satisfiability_boolean] is in [bpp] 6 - this is specific to >0 and does not work, say, for <2^n (problem of relative 7 error) 8 9 Proof: with proba 3/4 your [fpras] "works", and "works" here means "returns exactly the correct value" 10 11 Up: [result] on [fpras]