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

  • $\begingroup$ PP is contained in PSPACE. We can't separate NC$^1$ from PSPACE. $\endgroup$ Jun 10, 2020 at 7:01
  • $\begingroup$ Isn’t $NC_1$ contained in Logspace which is strictly contained in PSPACE? $\endgroup$ Jun 10, 2020 at 7:20
  • $\begingroup$ You might have a point... $\endgroup$ Jun 10, 2020 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$ Jun 10, 2020 at 7:24
  • $\begingroup$ Apparently PP can be separated from TC$^0$, but I doubt we can separate NC$^1$ from PP. $\endgroup$ Jun 10, 2020 at 7:25


Your Answer

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