2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 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, 2017 at 15:31
  • 1
    $\begingroup$ @JoshuaGrochow On broadness I tried to make specific queries now $\endgroup$
    – Turbo
    Apr 18, 2017 at 21:38

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.