8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Also I'd like to add that I can't think of how the reduction being intractable would lead to the problem being free of obstructions, how can one extend that idea? $\endgroup$ – dhillonv10 Aug 4 '11 at 17:09
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I see, thanks for that answer Josh. So basically it turns out that if one can reduce a given problem to a representation-theoretic form as shown in the GCT program, then one by the method of obstructions show that those classes are separable. In a general sense, it seems to me that it might be undecidable to show that no obstructions implies easy. $\endgroup$ – dhillonv10 Aug 7 '11 at 4:35
  • $\begingroup$ Even though I've closed the answer because the main question I had was regarding obstructions, I'd appreciate if you (@joshua-grochow) could comment on how postselection might play a role. Thanks. $\endgroup$ – dhillonv10 Aug 7 '11 at 4:47
  • $\begingroup$ @dhillonv10 I had a hard time understanding exactly what you were asking about postselection, but maybe it's just because I don't know very much about postselection yet. Sorry. $\endgroup$ – Joshua Grochow Aug 7 '11 at 14:41
  • $\begingroup$ np, thanks again though. $\endgroup$ – dhillonv10 Aug 8 '11 at 19:30
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for the insights Nathan, the main problem here is what you mention, there's no way to be absolutely sure that a problem has no obstructions, Mulmuley refers this to as the P-Barrier where finding some of the obstructions may take exponential time. $\endgroup$ – dhillonv10 Aug 4 '11 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.