# Should GCT focus on $PSPACE\not\subseteq P/poly$?

GCT tries to show $P$ is not $NP$ by showing $NP$ is not in $P/poly$.

Could it be useful in showing $\Sigma_{i+1}\not\subseteq P^{\Sigma_i}/Poly$ at every $i>0$?

Suppose if it turns out that $\Sigma_{i^*+1}=\Sigma_{i^*}$ at some $i^*>0$ then we automatically have $\Sigma_{i+1}\subseteq P^{\Sigma_i}/Poly$ at every $i$ at least $i^*$.

1. Since it would be reasonable to assume any technique for separation of $NP$ from $P/poly$ would be related to technique for showing $\Sigma_{i+1}\not\subseteq P^{\Sigma_i}/Poly$ (uniform proof transparent to $i$) would it have any indication showing GCT would not be sufficient for separating of $NP$ from $P/poly$?

Why do we want to show $NP\not\subseteq P/poly$ directly?

1. Instead of directly showing $NP\not\subseteq P/poly$ would it be easier to show $\Sigma_i\not\subseteq P/poly$ at some very large $i$ (perhaps $PSPACE$)?
• GCT = ... ​ ​ ​ – user6973 Jan 22 '18 at 3:21
• – Brout Jan 22 '18 at 3:25

Sure, in principle it could be used to separate the levels of $\mathsf{PH}$...the key thing is to find polynomial families complete for the relevant classes (or, at least polynomial families $f, g$ such that $f$ is in the larger class and is conjectured to not be in the smaller class, and such that showing that $f$ is not a projection of $g$ suffices to show that $f$ is not in the smaller class) that have nice symmetry properties. In practice, however, we know of very few natural complete problems for levels of $\mathsf{PH}$ beyond the second or third level, let alone problems with nice symmetry properties.
Q2: Indeed, the current focus of GCT and much of algebraic complexity is on permanent versus determinant, which is much closer to $\mathsf{\# P/poly}$ vs $\mathsf{FNC^2/poly}$ than it is to $\mathsf{NP}$ versus $\mathsf{P}$. As $\mathsf{\# P}$ is relatively close to $\mathsf{PSPACE}$ (and certainly above $\mathsf{PH}$), this is already in line with your suggestion.
Q1: Separating higher levels of $\mathsf{PH}$ from one another is formally harder than separating $\mathsf{NP}$ from $\mathsf{P}$. I'm not sure that it's reasonable to assume that any technique showing $\mathsf{NP} \not\subseteq \mathsf{P/poly}$ would be related to one for showing $\mathsf{\Sigma_i P} \not\subseteq \mathsf{\Delta_i P/poly}$. Indeed, the relativization barrier suggests that this shouldn't be the case. But also, even moving between the first and second levels of $\mathsf{PH}$ is currently nontrivial... So I don't really buy the premise for this question. But, also, I don't see any reason that GCT shouldn't apply to separate higher levels of $\mathsf{PH}$, nor any way to turn this around to show that GCT can't separate $\mathsf{NP}$ from $\mathsf{P/poly}$...
That all being said, if you look at Mulmuley's parallel lower bound in the PRAM model without bit operations, it not only shows that "$\mathsf{P} \neq \mathsf{NC}$" in that model, it also separates the levels of $\mathsf{NC}$ from one another in that model.