<p>Is it known $\mathsf{RNC=NC\iff P=RP}$ or $\mathsf{BPNC=NC\iff P=BPP}$?</p>

<p>Are there any analogies (such as collapse results, problems which suggest analogies such as gcd(in NC) and factoring (in P), potential analogies such as (perfect matching in BPNC as to something else in BPP etc) between $\mathsf{NC}$ hierarchy and $\mathsf{PH}$ hierarchy?</p>

CC BY-SA 3.0
2017-04-18T15:31:59.227Z
(1) RNC is the NC-analogue of RP, so as stated this seems unlikely, as its not even known that $P=RP \Leftrightarrow P=BPP$ (and proving such requires non-relativizing techniques: [Buhrman-Fortnow STACS '99](http://doi.org/10.1007/3-540-49116-3_9)). Maybe you want "BPNC=NC" on the LHS or "P=RP" on the RHS? (2) I think you mean "known analogies." (3) Your second question is very broad. (4) Related to your second question: https://cstheory.stackexchange.com/a/11403/129.
Joshua Grochow
CC BY-SA 3.0
2017-04-18T21:38:44.287Z
@JoshuaGrochow On broadness I tried to make specific queries now
Turbo
<big-picture><dc.parallel-comp><polynomial-hierarchy><hierarchy-theorems><time-hierarchy>
On analogies between parallel complexity and polynomial time hierarchy structure?
Turbo
# On analogies between parallel complexity and polynomial time hierarchy structure?

(Asked by: username_0 on 2017-04-17)

Is it known $\mathsf{RNC=NC\iff P=RP}$ or $\mathsf{BPNC=NC\iff P=BPP}$?

Are there any analogies (such as collapse results, problems which suggest analogies such as gcd(in NC) and factoring (in P), potential analogies such as (perfect matching in BPNC as to something else in BPP etc) between $\mathsf{NC}$ hierarchy and $\mathsf{PH}$ hierarchy?

**Tags:** big-picture, dc.parallel-comp, polynomial-hierarchy, hierarchy-theorems, time-hierarchy

> **Comments:**
> **username_1**: (1) RNC is the NC-analogue of RP, so as stated this seems unlikely, as its not even known that $P=RP \Leftrightarrow P=BPP$ (and proving such requires non-relativizing techniques: [Buhrman-Fortnow STACS '99](http://doi.org/10.1007/3-540-49116-3_9)). Maybe you want "BPNC=NC" on the LHS or "P=RP" on the RHS? (2) I think you mean "known analogies." (3) Your second question is very broad. (4) Related to your second question: https://cstheory.stackexchange.com/a/11403/129.  
> **username_0**: @JoshuaGrochow On broadness I tried to make specific queries now  

---

## 0 answers

