Classifying Papers On Classifying Problems
When are counting constraint problems easy and when are they hard
Richard Ladner is a complexity theorist, who after working in pure theory, later moved into more practical areas. In both areas he brought his expertise at problem solving to bear: in the former he proved seminal theorems, and in the later he created systems that have enhanced the lives of many with sight or hearing impairments.
Today I want to discuss some exciting developments in the classification of the complexity of counting problems. These results are related to the early work of Richard.
Ladner started his career in complexity theory where he made important and lasting contributions. He later shifted his focus to the area of creating accessible technologies for disabled persons. For example, he has worked making web browsing possible for sight impaired people, making understanding textbook pictures also accessible to them, and making cell phones useable for hearing impaired people via realtime sign language translation.
I have had the pleasure to meet Ladner’s parents who both are hearing impaired, who were both wonderful and kind to me. I have no doubt that they played some large role in helping him refocus his energies. While a theorem may be forever, the work that he has done in accessible technology has changed the lives of countless people. Thank you Richard.
One of Ladner’s beautiful theorems is the following from 1975:
Theorem: Suppose that . Then there is a language in so that is not -complete.
Possible conjectured candidates for the language are the decision version of factoring integers and graph isomorphism. The beauty of Ladner’s theorem is as long as , then there must be such intermediate languages. Whether or not they are natural problems of the kind we expect is another story, but they will always exist.
Decision and Counting Problems
A decision problem asks: is a set of objects X empty? A counting problem asks: how many objects X are there in a set? These sets are syntactically defined such as the satisfying assignments of a Boolean formula.
The decision problem and the counting problem are not related always in an obvious manner. There are cases where the decision problem is trivial, but the counting problem is hard: for example 2-. There are other cases where the decision problem and the counting problem are both easy. One of my favorites of this latter phenomena is the problem of counting the number of spanning trees in an undirected graph. This follows from the famous Matrix Tree Theorem of Gustav Kirchhoff, which reduces the counting problem to the evaluation of a determinant.
Do Not Give Up Too Easily
A meta question is: how can one tell if a decision problem or a counting problem is easy, specifically in polynomial time, or complete?
At this level of generality the problem is completely hopeless: if a problem of either type can be defined by an arbitrary procedure there is no hope to be able to tell whether the problem is hard or easy. More precisely Ladner’s theorem shows that there will be intermediate problems: some problems will be outside polynomial time, but still not complete. The same behavior can happen for counting problems.
Rule two of research is not to give up too easily—pretty cool to have all three “two’s” in the same sentence? If the general unrestricted question is impossible, then a good idea is to restrict the class of problems. This is exactly what has been done for both decision problems and counting problems. The high level idea is:
- Create a restrictive language for expressing decision and counting problems.
- Then show that it is possible to look at any problem that is expressed in this limited language and determine its computational complexity: whether it is in polynomial time or complete.
The exciting part of this research is there is a fine line. If the language used to express the problems is too strong, then one will fall into the tarpit—there will be no way to classify easy problems from hard ones. If the language used is too weak, then one may succeed, but the results will be not very interesting. A weak language will fail to capture enough interesting problems. This makes the research non-trivial and interesting.
A classification theorem consists of a language for defining a family of decision or counting problems, and a rule for deciding which problems are hard and which are easy. All the classification theorems I will discuss are stronger: they show that the problems are either in polynomial time or are complete for for decision problems and compete for for counting problems. Such theorems are sometimes called dichotomy theorems—no Ladner intermediate problems are allowed.
You can use these theorems as follows:
- Suppose you wish to know the complexity of counting the number of objects X that are in a certain family.
- You check if the property that defined the family can be expressed in the language allowed by the classification theorem.
- If the answer is yes, then you intermediately have an answer: you just check the theorem and see if the problem is easy or hard.
Pretty neat, pretty simple. Makes determining the complexity of a problem like looking up the value of a logarithm in a table. Almost mechanical.
Well almost. Some of the classification theorems give mathematical criterion, but these criterion are not always effective. Indeed one of the contributions has often been to show that the criterion can be made effective.
What is a suitable language for properties? Suppose that we are only interested in graphs and their properties. One idea is to define the properties by using the notion of graph homomorphism.
The notion of homomorphism is fundamental to mathematics. Let’s look at homomorphism’s on other structures, like groups. If are groups, then a homomorphism is a mapping so that
for all in . Here denotes the operation for the group and for the group .
These mappings are central to understanding the structure of groups. When the mapping is not one-to-one such maps are especially interesting. In this case they reveal many wonderful properties of the group. Graph homomorphism play the same role of revealing important information for graphs as algebraic homomorphism play for other structures.
The idea is that homomorphisms for graphs allows many interesting properties to be defined. While homomorphism were well studied for groups, rings, and other structures it was not as obvious that they can play a key role in graph theory. A graph homomorphism from a graph to a graph is defined by a mapping so that
At first it may seem that the definition is not really the same type as the group one—the difference is that in groups the operation is a function, while in graphs the “operation” is a relation. We could have defined group homomorphism by the rule:
This would make them both look alike.
As you probably expect many properties of graphs can be expressed as follows: a graph has property X provided there is some homomorphism from from to a particular graph . In this way it is easy to define the property, for example, of “3-colorable.” A graph is 3-colorable if and only if there is a homomorphism from to the triangle graph. Pavol Hell and Jaroslav Nešetřil have a book with many more details.
One of the reasons the notion of graph homomorphisms is so powerful is the following beautiful result of László Lovász who proved in 1967:
Theorem: Let and be finite graphs. Then and are isomorphic if and only if for all graphs ,
Here counts the number of homomorphisms from to . Thus counting the number of graph homomorphisms can be used to define a graph up to isomorphism.
Classification For Homomorphism
One basic problems is to determine when a property defined by counting the number of graph homomorphisms is either easy or complete. Let’s call this Constraint Satisfaction Problems (#CSP)—the name is selected because it really stands for a much larger class of properties. More on that later on.
For example, Martin Dyer, Leslie Goldberg and Mike Paterson proved a dichotomy when is restricted to be a directed acyclic graph. They showed that if is layered and satisfies a condition called Lovász goodness, then the corresponding restricted #CSP is computable in polynomial time; otherwise it is #P-hard. Below are two examples. The first is a good graph,
and the second is a bad graph:
Check the paper for the definition of what is good and what is bad.
Classification For Generalized Homomorphism
There is a natural way using weights and more to generalize the notion of graph homomorphism. I will not define this notion of a full fledged #CSP, see here for the details. The excitement is that there are three recent complexity dichotomy theorems in this area. They completely classify the worst-case complexity of every possible counting #CSP problem. It is interesting to note that the corresponding decision problem remains open: this is a case where we know more about counting problems than decision problems.
The first big result is due to Andrei Bulatov. Over the years, Bulatov and others have built a formidable machinery which has been called the Algebraic Approach. The distinguishing feature is the heavy reliance on Universal Algebra. In a 2008 paper Bulatov gave a dichotomy theorem for all #CSP problems where the constraint functions take 0-1 values. This proof uses deep structural theorems from Universal Algebra, in particular the so-called commutator theory and tame congruence theory.
Then Martin Dyer and David Richerby in their paper gave an alternative proof of Bulatov’s dichotomy theorem for unweighted #CSP. Notably, their proof uses no universal algebra other than the notion of Mal’tsev polymorphisms.
The newest dichotomy theorem is by Jin-Yi Cai, Xi Chen and Pinyan Lu and is available here. It gives a complete classification for all non-negatively weighted #CSP’s. A feature of their theorem is that, while it is more general than previous theorems, surprisingly the criterion for tractability becomes simpler than the previous ones, and the proof uses virtually no universal algebra.
The new results on #CSP have powerful consequences. They completely characterize the complexity of counting directed graph homomorphisms. They give us new tractable cases. For example, the following graph defines a binary predicate on domain size 8, and it is not layered and not acyclic. The fact that it is tractable in polynomial time is far from obvious, and is implied by the new dichotomy theorem.
I have written in the past on the beautiful paper by Cai, Chen and Lu that proves an earlier complexity dichotomy theorem. That theorem is not superseded by the new results. That tour de force (which is over 100 pages) is intimidatingly weighty; it dealt with undirected graph homomorphisms with arbitrary complex weights. When the constraint functions are no longer restricted to taking only non-negative values, the problem is even more challenging and also more fascinating. Just think of monotone circuit complexity versus general circuit complexity.
The main open problem is to unify all this information about counting problems into one framework. I expect this will be hard, but that we will see progress on it.
[fixed link to Cai-Chen-Lu.]