2
$\begingroup$

We know that for every counting problem $\#A$ in $\#P$, there is a probabilistic algorithm $\mathcal C$ that on input $x$, computes with high probability a value $v$ such that $$(1 − ε)\#A(x) ≤ v ≤ (1 + ε)\#A(x)$$ in time polynomial in $|x|$ and within $\frac1ε$ multiplicative factor, using an oracle for $NP$.

That is $\#P$ can be approximated in $BPP^{NP}$.

What is the best derandomization result for this that is known?

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.