1
$\begingroup$

Is $NC_1$ vs PP still an open problem? I done a few searched but I can't find an answer.

$\endgroup$
6
  • $\begingroup$ PP is contained in PSPACE. We can't separate NC$^1$ from PSPACE. $\endgroup$ – Yuval Filmus Jun 10 '20 at 7:01
  • $\begingroup$ Isn’t $NC_1$ contained in Logspace which is strictly contained in PSPACE? $\endgroup$ – blademan9999 Jun 10 '20 at 7:20
  • $\begingroup$ You might have a point... $\endgroup$ – Yuval Filmus Jun 10 '20 at 7:22
  • $\begingroup$ The only proof techniques we currently have is hierarchy theorems (which separate L from PSPACE), combinatorial techniques (which give lower bounds against circuits with depth up to roughly $\log n/\log\log n$), and diagonalization (Ryan Williams' method), which is useful for classes such as ACC. $\endgroup$ – Yuval Filmus Jun 10 '20 at 7:24
  • $\begingroup$ Apparently PP can be separated from TC$^0$, but I doubt we can separate NC$^1$ from PP. $\endgroup$ – Yuval Filmus Jun 10 '20 at 7:25

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.