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?

  • 2
    $\begingroup$ (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. $\endgroup$ – Joshua Grochow Apr 18 '17 at 15:31
  • 1
    $\begingroup$ @JoshuaGrochow On broadness I tried to make specific queries now $\endgroup$ – 1.. Apr 18 '17 at 21:38

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.