Self-reducible with easy decision version counting problems admit additive error approximation. Connections to counting complexity, exponential time complexity, and circuit lower bounds

Eleni Bakali

We consider the class of counting problems,i.e. functions in $\#$P, which are self reducible, and have easy decision version, i.e. for every input it is easy to decide if the value…