<p>No, the unavoidability of constructivity definitely still leaves GCT open as a viable plan of attack on lower bound problems such as $NP$ vs. $P/poly$.</p>

<p>First, it is worth mentioning that Ryan's result on constructivity is very similar in flavor to the so-called "Flip Theorems" by Mulmuley, which say, for example, that if permanent does not have poly-size arithmetic circuits, then there is a randomized poly-time constructible set of (polynomially many) matrices $\{M_1, \dotsc, M_{p(n)}\}$ such that every small circuit differs from the permanent on one of these matrices. See <a href="http://gct.cs.uchicago.edu/gctflip.ps" rel="nofollow noreferrer"> Explicit Proofs and The Flip, Technical Report, Computer Science Department, The University of Chicago, September 2010</a> by Mulmuley.</p>

<p>Second, the centrality of symmetry-characterization (mentioned already by siuman) in GCT has become more apparent since Regan's survey. If symmetry-characterization turns out to be as crucial to GCT as it seems like it is going to, then this already gets around the largeness condition. For the definition of symmetry-characterzation, see <a href="https://cstheory.stackexchange.com/a/186/129">this answer</a> to a closely related <a href="https://cstheory.stackexchange.com/q/170/129">previous question</a>. </p>

<p>For a proof that symmetry-characterization violates largeness, see Section 3.4.3 "Symmetry-characterization avoids the Razborov–Rudich barrier" in <a href="http://www.cs.toronto.edu/~jgrochow/grochow-thesis.pdf" rel="nofollow noreferrer">my thesis</a> (shameless self plugs, but I don't know anywhere else where this is written down so completely). I suspect it also violates constructivity, but left that as an open question there. (Earlier in Chapter 3 there's also an overview of the flip theorems in GCT and how they relate to symmetry-characterization.)</p>

<p>(I find it interesting that symmetry-characterization - the very property we suspect will be used in GCT that gets around Razborov--Rudich - is used to prove the flip theorems, which essentially say that constructivity is necessary.)</p>

<p>Finally, it is worth mentioning that although in the long run GCT aims to address $NP$ versus $P/poly$ and other Boolean problems, at the moment most work in GCT is focused on algebraic analogs of these, such as over the complex numbers, and there is as yet no algebraic analog of Razborov--Rudich (that I know of).</p>

CC BY-SA 3.0
2013-01-06T05:43:31.777Z
Josh: my meager understanding is that Mulmuley's results of the form "permanent does not have polysize circuits implies polynomial-time obstructions for permanent" also require an additional derandomization hypothesis, say for PIT. (But it is an interesting question: is such a derandomization hypothesis even required, if we are already assuming the permanent doesn't have small circuits?)
Thanks for the pointer to your thesis!
Ryan Williams
CC BY-SA 3.0
2013-01-07T21:12:43.900Z
@RyanWilliams: Yes, that is correct. I'll update the answer now to say "randomized poly time."
Joshua Grochow
CC BY-SA 3.0
2013-01-05T19:52:53.573Z
2013-01-07T21:13:04.413Z
2017-04-13T12:32:28.077Z
Joshua Grochow
<p>Let me first correct a possible misunderstanding: unfortunately we don't know yet that $NEXP \not\subset TC^0$. My most recent lower bound is $NEXP \cap coNEXP \not\subset ACC$. </p>

<p>Now, the answer to your question is no. It is still very possible that techniques based on GCT can separate $P$ from $NP$. </p>

<p>A few more comments about this: the relation between GCT and Natural Proofs has been discussed in the past (even in the original GCT papers themselves). While there does not seem to have been consensus about which of "constructivity" or "largeness" would be violated by the GCT approach, Mulmuley and Sohoni did argue at one point that if GCT could be carried out then it should violate largeness. For a relevant reference, see Section 6 of <a href="http://www.cse.buffalo.edu/~regan/papers/pdf/Reg02MSFD.pdf">Regan's overview of GCT</a>. However, I should add that this overview is already 10 years old, and a considerable amount of work has gone into GCT since then; I am not sure if there is any revised/new opinion on this. (Perhaps Josh Grochow can chime in?)</p>

CC BY-SA 3.0
2013-01-04T18:44:58.840Z
2013-01-04T18:44:58.840Z
Ryan Williams
<p>The short answer is <strong>No</strong>.</p>

<p>The Geometric Complexity Theory approach targets certain extremely rare property, which Mulmuley argues is not "large" as defined by Razborov and Rudich. For a formal argument, see also Joshua Grochow's <a href="http://www.cs.toronto.edu/~jgrochow/grochow-thesis.pdf" rel="nofollow noreferrer">thesis</a>, Section 3.4.3 <em>Symmetry-characterization avoids the Razborov–Rudich barrier</em>, and his <a href="https://cstheory.stackexchange.com/a/14978/13218">answer</a>.</p>

<p>The following paragraph comes from <em>On P vs. NP and Geometric Complexity Theory</em> by Ketan Mulmuley (<a href="http://dx.doi.org/10.1145/1944345.1944346" rel="nofollow noreferrer">JACM 2011</a> or <a href="http://ramakrishnadas.cs.uchicago.edu/gctexplicit.pdf" rel="nofollow noreferrer">manuscript</a>), Section 4.3 <em>A High Level Plan</em>:</p>

<blockquote>
  <p>The goal is to carry out these steps explicitly, exploiting the characterization by
  symmetries of the permanent and determinant. We shall specify what explicit means
  later; cf. Hypothesis 4.6. This approach is extremely rigid in the sense that it only
  works for extremely rare hard functions that are characterized by their symmetries.
  This extreme rigidity is much more than what is needed to bypass the natural proof
  barrier [Razborov and Rudich 1997].</p>
</blockquote>

<p>Since both the conditions of constructivity and largeness are required for a natural proof (where usefulness is implicit), proving that constructivity is unavoidable is not sufficient to rule out such approaches (though a big step forward).</p>

CC BY-SA 3.0
2013-01-04T19:23:40.553Z
2013-01-06T05:50:27.003Z
2017-04-13T12:32:28.167Z
siuman
<p>Recently, Ryan Willams proved that Constructivity in Natural Proof is unavoidable to derive a separation of complexity classes : $\mathsf{NEXP}$ and $\mathsf{TC}^{0}$.   </p>

<p>Constructivity in Natural Proof is a condition that all combinatorial proofs in circuit complexity satisfies and that we can decide whether the target function in $\mathsf{NEXP}$ (or another "hard" complexity classes) has a "hard" property by a algorithm that runs in poly-time in the length of target function's truth table.</p>

<p>The other two conditions are: useless condition that require "hard" property can not be computed by any circuits in $\mathsf{TC}^0$ and largeness condition that the hard property is easy to find.</p>

<p>My question is :</p>

<p>Does this result make the Geometric Complexity Theory (GCT) unavailable to resolve main separation problems such as $\mathsf{P}$ vs $\mathsf{NP}$, $\mathsf{P}$ vs $\mathsf{NC}$, or $\mathsf{NEXP}$ vs $\mathsf{TC}^0$?</p>

<p>References:  </p>

<ul>
<li>Ryan Williams, "<a href="http://arxiv.org/abs/1212.1891" rel="nofollow">Natural Proofs Versus Derandomization</a>"</li>
</ul>

<cc.complexity-theory><complexity-classes><circuit-complexity><gct><barriers>
Constructivity in Natural Proof and Geometric Complexity
auyun
# Constructivity in Natural Proof and Geometric Complexity

(Asked by: username_0 on 2013-01-04)

Recently, Ryan Willams proved that Constructivity in Natural Proof is unavoidable to derive a separation of complexity classes : $\mathsf{NEXP}$ and $\mathsf{TC}^{0}$.

Constructivity in Natural Proof is a condition that all combinatorial proofs in circuit complexity satisfies and that we can decide whether the target function in $\mathsf{NEXP}$ (or another "hard" complexity classes) has a "hard" property by a algorithm that runs in poly-time in the length of target function's truth table.

The other two conditions are: useless condition that require "hard" property can not be computed by any circuits in $\mathsf{TC}^0$ and largeness condition that the hard property is easy to find.

My question is :

Does this result make the Geometric Complexity Theory (GCT) unavailable to resolve main separation problems such as $\mathsf{P}$ vs $\mathsf{NP}$, $\mathsf{P}$ vs $\mathsf{NC}$, or $\mathsf{NEXP}$ vs $\mathsf{TC}^0$?

References:

* Ryan Williams, "[Natural Proofs Versus Derandomization](http://arxiv.org/abs/1212.1891)"

**Tags:** cc.complexity-theory, complexity-classes, circuit-complexity, gct, barriers

---

## 3 answers

### Answer by username_1 on 2013-01-05. Score: 20

No, the unavoidability of constructivity definitely still leaves GCT open as a viable plan of attack on lower bound problems such as $NP$ vs. $P/poly$.

First, it is worth mentioning that Ryan's result on constructivity is very similar in flavor to the so-called "Flip Theorems" by Mulmuley, which say, for example, that if permanent does not have poly-size arithmetic circuits, then there is a randomized poly-time constructible set of (polynomially many) matrices $\{M\_1, \dotsc, M\_{p(n)}\}$ such that every small circuit differs from the permanent on one of these matrices. See  [Explicit Proofs and The Flip, Technical Report, Computer Science Department, The University of Chicago, September 2010](http://gct.cs.uchicago.edu/gctflip.ps) by Mulmuley.

Second, the centrality of symmetry-characterization (mentioned already by siuman) in GCT has become more apparent since Regan's survey. If symmetry-characterization turns out to be as crucial to GCT as it seems like it is going to, then this already gets around the largeness condition. For the definition of symmetry-characterzation, see [this answer](https://cstheory.stackexchange.com/a/186/129) to a closely related [previous question](https://cstheory.stackexchange.com/q/170/129).

For a proof that symmetry-characterization violates largeness, see Section 3.4.3 "Symmetry-characterization avoids the Razborov–Rudich barrier" in [my thesis](http://www.cs.toronto.edu/~jgrochow/grochow-thesis.pdf) (shameless self plugs, but I don't know anywhere else where this is written down so completely). I suspect it also violates constructivity, but left that as an open question there. (Earlier in Chapter 3 there's also an overview of the flip theorems in GCT and how they relate to symmetry-characterization.)

(I find it interesting that symmetry-characterization - the very property we suspect will be used in GCT that gets around Razborov--Rudich - is used to prove the flip theorems, which essentially say that constructivity is necessary.)

Finally, it is worth mentioning that although in the long run GCT aims to address $NP$ versus $P/poly$ and other Boolean problems, at the moment most work in GCT is focused on algebraic analogs of these, such as over the complex numbers, and there is as yet no algebraic analog of Razborov--Rudich (that I know of).

> **Comments:**
> **username_2**: Josh: my meager understanding is that Mulmuley's results of the form "permanent does not have polysize circuits implies polynomial-time obstructions for permanent" also require an additional derandomization hypothesis, say for PIT. (But it is an interesting question: is such a derandomization hypothesis even required, if we are already assuming the permanent doesn't have small circuits?) Thanks for the pointer to your thesis!  
> **username_1**: @RyanWilliams: Yes, that is correct. I'll update the answer now to say "randomized poly time."  

---

### Answer by username_2 on 2013-01-04. Score: 17

Let me first correct a possible misunderstanding: unfortunately we don't know yet that $NEXP \not\subset TC^0$. My most recent lower bound is $NEXP \cap coNEXP \not\subset ACC$.

Now, the answer to your question is no. It is still very possible that techniques based on GCT can separate $P$ from $NP$.

A few more comments about this: the relation between GCT and Natural Proofs has been discussed in the past (even in the original GCT papers themselves). While there does not seem to have been consensus about which of "constructivity" or "largeness" would be violated by the GCT approach, Mulmuley and Sohoni did argue at one point that if GCT could be carried out then it should violate largeness. For a relevant reference, see Section 6 of [Regan's overview of GCT](http://www.cse.buffalo.edu/~regan/papers/pdf/Reg02MSFD.pdf). However, I should add that this overview is already 10 years old, and a considerable amount of work has gone into GCT since then; I am not sure if there is any revised/new opinion on this. (Perhaps Josh Grochow can chime in?)


---

### Answer by username_3 on 2013-01-04. Score: 14

The short answer is **No**.

The Geometric Complexity Theory approach targets certain extremely rare property, which Mulmuley argues is not "large" as defined by Razborov and Rudich. For a formal argument, see also Joshua Grochow's [thesis](http://www.cs.toronto.edu/~jgrochow/grochow-thesis.pdf), Section 3.4.3 *Symmetry-characterization avoids the Razborov–Rudich barrier*, and his [answer](https://cstheory.stackexchange.com/a/14978/13218).

The following paragraph comes from *On P vs. NP and Geometric Complexity Theory* by Ketan Mulmuley ([JACM 2011](http://dx.doi.org/10.1145/1944345.1944346) or [manuscript](http://ramakrishnadas.cs.uchicago.edu/gctexplicit.pdf)), Section 4.3 *A High Level Plan*:

> The goal is to carry out these steps explicitly, exploiting the characterization by
> symmetries of the permanent and determinant. We shall specify what explicit means
> later; cf. Hypothesis 4.6. This approach is extremely rigid in the sense that it only
> works for extremely rare hard functions that are characterized by their symmetries.
> This extreme rigidity is much more than what is needed to bypass the natural proof
> barrier [Razborov and Rudich 1997].

Since both the conditions of constructivity and largeness are required for a natural proof (where usefulness is implicit), proving that constructivity is unavoidable is not sufficient to rule out such approaches (though a big step forward).


---

