<p>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.</p>

<p>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.</p>

<p>Q1: Separating higher levels of $\mathsf{PH}$ from one another is formally <em>harder</em> 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}$...</p>

<p>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.</p>

CC BY-SA 3.0
2018-01-22T04:31:33.423Z
2018-01-22T04:31:33.423Z
Joshua Grochow
<p>GCT tries to show $P$ is not $NP$ by showing $NP$ is not in $P/poly$.</p>

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

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

<ol>
<li>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$?</li>
</ol>

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

<ol start="2">
<li>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$)?</li>
</ol>

CC BY-SA 3.0
2018-01-22T03:25:34.993Z
https://en.wikipedia.org/wiki/Geometric_complexity_theory.
Turbo
<cc.complexity-theory><complexity-classes><circuit-complexity><lower-bounds><gct>
Should GCT focus on $PSPACE\not\subseteq P/poly$?
Turbo
# Should GCT focus on $PSPACE\not\subseteq P/poly$?

(Asked by: username_0 on 2018-01-22)

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?

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

**Tags:** cc.complexity-theory, complexity-classes, circuit-complexity, lower-bounds, gct
> **Comments:**
> **username_0**: https://en.wikipedia.org/wiki/Geometric_complexity_theory.  

---

## 1 answers

### Answer by username_1 on 2018-01-22. Score: 7

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.


---

