# On analogies between parallel complexity and polynomial time hierarchy structure?

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?

• (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). 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: cstheory.stackexchange.com/a/11403/129. – Joshua Grochow Apr 18 '17 at 15:31
• @JoshuaGrochow On broadness I tried to make specific queries now – 1.. Apr 18 '17 at 21:38