# Constructivity in Natural Proof and Geometric Complexity

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:

-

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

-
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 Jan 6 '13 at 5:43
@RyanWilliams: Yes, that is correct. I'll update the answer now to say "randomized poly time." –  Joshua Grochow Jan 7 '13 at 21:12

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

-