Is $NC_1$ vs PP still an open problem? I done a few searched but I can't find an answer.
$\begingroup$
$\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
|
Show 1 more comments
