Dichotomy 2

This post is a sort of continuation of my previous ramblings about dichotomy theorems.

Recall that Schaefer's Theorem essentially says that every boolean constraint satisfaction problem (CSP) is either in P or NP-Complete. Is there any real content to this? That is, if P is not equal to NP, then is there anything in between? The answer to this question is given by a famous result due to Richard Ladner - if P is not NP, then there is an incomplete set in NP - P. That is, there is a problem which is in NP, but in neither P nor NP-Complete. This result is contained in:

On the Structure of Polynomial Time Reducibility; Richard E. Ladner

A nice follow-up paper, which includes a succint account of two proofs of Ladner's Theorem in an appendix is:

Uniformly Hard Languages; Rod Downey and Lance Fortnow

Actually, Ladner's Theorem says that there would be a dense hierarchy of sets between P and NP. So, somehow Schaefer managed to home in on a large piece of NP that skips out anything in between P and NP, whether there is anything there or not. I previously pointed to some articles that look to extend Schaefer's theroem to broader classes of CSP's by translating everything into universal algebra.

Another approach is given in the following remarkable paper (with an unfortunately long title!):

The Computational Structure of Monotone Monadic SNP and Constraint Satisfiaction: A Study Through Datalog and Group Theory; Tomas Feder and Moshe Vardi

Their approach is to start from Fagin's Theorem, which says that NP is precisely the class of languages expressible in existensial second order logic. By placing increasingly many syntactic restrictions on the language they use, they eventually end up with a logic which does not seem to fall prey to Ladner's Theorem. This logic then turns out to be equivalent to the class of CSP problems, though one direction of the equivalence uses a randomised reduction (it is an enticing open problem to derandomise this).

The article does not really succeed in identifying a large subclass of NP that has a dichotomy theorem. What it does do, however, is to explain the various cases of Schaefer's theorem and why each of them are polynomial, in a manner which facilitates generalisation. What they discovered is that "linear equations mod 2" is polynomial for a very different reason to the other cases. Rather than summarise their results (of which there are many!), I'll just point you to slides for a talk that I gave recently on the topic:

Deeper into Dichotomy: Splitting the Computational Universe; Jon Cohen

I tend to say a lot more in a talk than is on my slides and this talk was no exception. One thing I mentioned that is not on the slides is a neat dichotomy result from combinatorics. Consider the problem of deciding whether it is possible to colour the vertices of a graph with three or fewer colours in such a way that no two adjacent vertices have the same colour (that is, the 3-colourability problem). If you squint a bit, then you'l see that this is the same as asking if there is a homomorphism from the graph you are interested in, to the complete graph on three vertices, K3. To see this, just paint each vertex of K3 with a different colour and remember that there are no self-loops.

So, we have turned the colourability problem into a homomorphism problem. Now, there is nothing wrong with varying the target graph. What you get is the H-colouring problem. If the target graph is a complete graph, then you just get the standard k-colourability problem. It turns out that, depending upon the type of the target graph, we get a dichotomy! That is, if the target graph is bipartite, then the H-Colourability problem is in P, otherwise it is NP-Complete. This result is contained in:

On the Complexity of H-Coloring; P. Hell and J. Nesetril, J. Combin. Theory Ser. B, 48 (1990) pp. 92--110.

Anyway, there is loads of interesting stuff in Feder and Vardi's paper and it is well worth checking out if you are interested in the interaction between logic, complexity theory and group theory!