All Questions
Tagged with derandomization polynomial-hierarchy
4 questions
3
votes
0
answers
121
views
On approximating problems in $\#P$
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 ...
- 13.3k
3
votes
1
answer
156
views
On $\Delta_i^P$
We know $P\subseteq NP\cap coNP\subseteq\Delta_i^P=P^{\Sigma_{i-1}^P}\subseteq \Sigma_i^P\cap\Pi_i^P=NP^{\Sigma_{i-1}^P}\cap coNP^{\Sigma_{i-1}^P}$.
If $P=BPP$ is there a 'higher' randomized class ...
- 13.3k
4
votes
0
answers
190
views
On earlier references for $P=BPP$ and Kolmogorov's possible view on modern breakthroughs involving randomness?
Kolmogorov and Uspenskii in this paper 'http://epubs.siam.org/doi/pdf/10.1137/1132060' speculate P=BPP in 1986. They do this without getting into circuit lower bounds and from a different view which ...
- 13.3k
13
votes
1
answer
297
views
When does randomization stops helping within PSPACE
It is known that adding bounded-error randomization to PSPACE doesn't add power. That is, BPPSAPCE=PSPACE.
It is famously unknown whether P=BPP, but it is known that $BPP\subseteq \Sigma_2\cap \Pi_2$....
- 5,636