Constructivity in Natural Proof and Geometric Complexity

Question

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"

Answer 1

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 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 to a closely related previous question.

For a proof that symmetry-characterization violates largeness, see Section 3.4.3 "Symmetry-characterization avoids the Razborov–Rudich barrier" in my thesis (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).

Answer 2

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. 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 3

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, Section 3.4.3 Symmetry-characterization avoids the Razborov–Rudich barrier, and his answer.

The following paragraph comes from On P vs. NP and Geometric Complexity Theory by Ketan Mulmuley (JACM 2011 or manuscript), 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).