Postselection in geometric complexity theory

Question

Context: As I understand, in geometric complexity theory, the existence of obstructions serves as a proof-certificate, so to speak, for the nonexistence of an efficient computational circuit for the explicit hard function in the lower bound problem under consideration. Now there are some other assumptions for obstructions that they must be short, easy to verify and easy to construct.

Question: My question is that say I have a problem that I conjecture to be solvable in polynomial time. Then how can I show that there exist no obstruction for this problem, i.e. if no obstructions exist then the problem can be computed efficiently and it is indeed in polynomial time.

Approach: I think, and I may be wrong in this assertion, that showing no obstructions exist can be equivalent to standard reduction of NP problems to other problems whose complexity is yet unknown, in the proof that they themselves are in NP. So then in that case one can, if possible, show that obstructions exist as one tries to reduce an NP problem to the problem under consideration, that way, the reduction is intractable. Also what role does postselection play in all of this? Is it possible to simply postselect on the nonexistence of obstructions? Thanks and pardon the lack of precise statements in my approach and questions.

Just an another example, consider a problem X that we know to be in P. Now let's say we didn't know about that problem being solvable in polynomial time, then is it possible, that one can make the following assertion:

Since no obstructions exist in the computation of X we can say that it is in the class P

From there on, the problem is the easy (computationally) discovery of those obstructions, if even one exists, would show that X is not in polynomial time. However going the other way, i.e. finding that no obstructions exist is a difficult task.

Answer 1

It depends what you mean by "exists no obstruction." If you mean "obstruction" in the general sense of some sort of proof certificate that the problem is not in $P$, then I have no idea how to answer your question because the notion of "obstruction" is still vague. If you mean "obstruction" specifically in the representation-theoretic sense of Mulmuley-Sohoni, then here is the answer:

For the purposes of this answer, we can partition the Mulmuley-Sohoni GCT program into two steps:

1. Associate to $perm$ and $det$ (or your favorite complexity classes) algebraic varieties $V_{perm}$ and $V_{det}$ in such a way that $V_{perm} \subseteq V_{det}$ if and only if $perm$ is a $p$-projection of $det$.

2. Find representation-theoretic obstructions to show that in fact $V_{perm} \not\subseteq V_{det}$.

Note that the implication in (2) only goes one direction (existence of obstruction implies no inclusion of varieties), so it is possible that $perm$ is not a $p$-projection of $det$ and yet no representation-theoretic obstructions exist. So in this case, just proving that no obstructions exist is not enough to show that $perm$ is easy. On the other hand, in (1) the inclusion of algebraic varieties is both necessary and sufficient for the inclusion of complexity classes.

[In the above of course many details have been omitted - the reliance on the input size, how to talk about the complexity class $P$ instead of $det$, the fact that the inclusion of varieties is equivalent to $perm$ being approximable by $p$-projections of $det$, ... But the essence is still right.]

Answer 2

I like to think this way too, and I link it with the $P=NP\cap co-NP$ conjecture. It is mentionned there or there (I am having a hard time finding pages about this conjecture as I can only refer to it with math symbols that Google does not like).

A problem is in NP when you can give a certificate for a "True" answer (example : a hamiltonian cycle for the TSP problem or a valid assignment for the SAT problem). It is in co-NP when you can give a certificate for a "False" answer (example : a "proof" that the SAT formula is not satisfiable, a bad cut in a graph that prevents the existence of a hamiltonian cycle, etc...)

Actually, those may be the "obstructions" you may refer too. And this conjecture is about saying : a problem which is in NP is polynomial when I know what the obstructions are.

Now, the "obstructions" can take many different forms. For the matching problem (which is polynomial) it can be a partition of the graph (see Tutte's characterization of graphs admitting a perfect matching), or it can be the certificate given by Farkas's Lemma for linear programming (and graph problems that can be reduced to it). It can actually be a great many things, and so I usually "use" this conjecture in one direction : When I can find no obstructions, I do not deduce that my problem is NP-Hard. Some obstructions are really hard to find... But when I have a complicated polynomial algorithm for a problem, I am sometimes convinced that "there must be an understandable set of obstructions, which would be easier to understand that the complicated algorithm".

Well... My two cents :-)

Nathann