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$)?

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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.