English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the class of counting problems,i.e. functions in $\#$P, which areself reducible, and have easy decision version, i.e. for every input it is easyto decide if the value of the function $f(x)$ is zero. For example,$\#$independent-sets of all sizes, is such a problem, and one of the hardest ofthis class, since it is equivalent to $\#$SAT under multiplicativeapproximation preserving reductions.  Using these two powerful properties, self reducibility and easy decision, weprove that all problems/ functions $f$ in this class can be approximated inprobabilistic polynomial time within an absolute exponential error$\epsilon\cdot 2^{n'}, \forall\epsilon>0$, which for many of those problems(when $n'=n+$constant) implies additive approximation to the fraction$f(x)/2^n$. (Where $n'$ is the amount of non-determinism of some associatedNPTM).  Moreover we show that for all these problems we can have multiplicative errorto the value $f(x)$, of any desired accuracy (i.e. a RAS), in time of order$2^{2n'/3}poly(n)$, which is strictly smaller than exhaustive search. We alsoshow that $f(x)<g(x)$ can be decided deterministically in time $g(x)poly(n),\forall g$.  Finally we show that the Circuit Acceptance Probability Problem, which isrelated to derandomization and circuit lower bounds, can be solved with highprobability and in polynomial time, for the family of all circuits for whichthe problems of counting either satisfying or unsatisfying assignments belongto TotP (which is the Karp-closure of self reducible problems with easydecision version).

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