Overarching reasons why problems are in P or BPP

Question

Recently, when talking to a physicist, I claimed that in my experience, when a problem that naively seems like it should take exponential time turns out nontrivially to be in P or BPP, an "overarching reason" why the reduction happens can typically be identified---and almost always, that reason belongs to a list of a dozen or fewer "usual suspects" (for example: dynamic programming, linear algebra...). However, that then got me to thinking: can we actually write down a decent list of such reasons? Here's a first, incomplete attempt at one:

(0) Mathematical characterization. Problem has a non-obvious "purely-mathematical" characterization that, once known, makes it immediate that you can just do exhaustive search over a list of poly(n) possibilities. Example: graph planarity, for which an O(n⁶) algorithm follows from Kuratowski's theorem.

(As "planar" points out below, this was a bad example: even once you know a combinatorial characterization of planarity, giving a polynomial-time algorithm for it is still quite nontrivial. So, let me substitute a better example here: how about, say, "given an input n written in binary, compute how many colors are needed to color an arbitrary map embedded on a surface with n holes." It's not obvious a priori that this is computable at all (or even finite!). But there's a known formula giving the answer, and once you know the formula, it's trivial to compute in polynomial time. Meanwhile, "reduces to excluded minors / Robertson-Seymour theory" should probably be added as a separate overarching reason why something can be in P.)

Anyway, this is specifically not the sort of situation that most interests me.

(1) Dynamic programming. Problem can be broken up in a way that enables recursive solution without exponential blowup -- often because the constraints to be satisfied are arranged in a linear or other simple order. "Purely combinatorial"; no algebraic structure needed. Arguably, graph reachability (and hence 2SAT) are special cases.

(2) Matroids. Problem has a matroid structure, enabling a greedy algorithm to work. Examples: matching, minimum spanning tree.

(3) Linear algebra. Problem can be reduced to solving a linear system, computing a determinant, computing eigenvalues, etc. Arguably, most problems involving "miraculous cancellations," including those solvable by Valiant's matchgate formalism, also fall under the linear-algebraic umbrella.

(4) Convexity. Problem can be expressed as some sort of convex optimization. Semidefinite programming, linear programming, and zero-sum games are common (increasingly-)special cases.

(5) Polynomial identity testing. Problem can be reduced to checking a polynomial identity, so that the Fundamental Theorem of Algebra leads to an efficient randomized algorithm -- and in some cases, like primality, even a provably-deterministic algorithm.

(6) Markov Chain Monte Carlo. Problem can be reduced to sampling from the outcome of a rapidly-mixing walk. (Example: approximately counting perfect matchings.)

(7) Euclidean algorithm. GCD, continued fractions...

Miscellaneous / Not obvious exactly how to classify: Stable marriage, polynomial factoring, membership problem for permutation groups, various other problems in number theory and group theory, low-dimensional lattice problems...

My question is: what are the most important things I've left out?

To clarify:

• I realize that no list can possibly be complete: whatever finite number of reasons you give, someone will be able to find an exotic problem that's in P but not for any of those reasons. Partly for that reason, I'm more interested in ideas that put lots of different, seemingly-unrelated problems in P or BPP, than in ideas that only work for one problem.

• I also realize that it's subjective how to divide things up. For example, should matroids just be a special case of dynamic programming? Is solvability by depth-first search important enough to be its own reason, separate from dynamic programming? Also, often the same problem can be in P for multiple reasons, depending on how you look at it: for example, finding a principal eigenvalue is in P because of linear algebra, but also because it's a convex optimization problem.

In short, I'm not hoping for a "classification theorem" -- just for a list that usefully reflects what we currently know about efficient algorithms. And that's why what interests me most are the techniques for putting things in P or BPP that have broad applicability but that don't fit into the above list -- or other ideas for improving my crude first attempt to make good on my boast to the physicist.

Answer 1

Lattice-basis reduction (LLL algorithm). This the basis for efficient integer polynomial factorization and some efficient cryptanalytic algorithms like breaking of linear-congruential generators and low-degree RSA. In some sense you can view the Euclidean algorithm as a special case.

Answer 2

Some graph classes allow polynomial-time algorithms for problems that are NP-hard for the class of all graphs. For instance, for perfect graphs, one can find a largest independent set in polynomial time (thanks to vzn in a comment for jogging my memory). Via a product construction, this also allows a unified explanation for several apparently quite different CSPs being tractable (such as those with tree structure which are usually solved by hierarchical decomposition, and the All-Different constraint that is usually solved by perfect matching).

It could be argued that perfect graphs are "easy" because they allow nice semidefinite programming formulations of the problems in question (and therefore fall under linear algebra and/or convexity). However, I'm not sure that completely captures what is going on.

• András Z. Salamon and Peter G. Jeavons, Perfect constraints are tractable, CP 2008, LNCS 5202, 524–528. doi:10.1007/978-3-540-85958-1_35

• Meinolf Sellmann, The Polytope of Tree-Structured Binary Constraint Satisfaction Problems, CPAIOR 2008, LNCS 5015, 367–371. doi:10.1007/978-3-540-68155-7_39

---

As noted by Gil Kalai, properties of graphs that form minor-closed classes can be defined by a finite set of forbidden minors (this is the Robertson-Seymour theorem). Another result of Robertson and Seymour is that testing for the presence of a minor can be done in cubic time. Together these lead to a polynomial-time algorithm to decide properties that are minor-closed.

• Neil Robertson and P. D. Seymour, Graph Minors. XIII. The disjoint paths problem, Journal of Combinatorial Theory, Series B 63(1) 65–110, 1995. doi:10.1006/jctb.1995.1006

One problem with minor-closed graph properties is that they are "small"; excluding even one minor excludes lots of graphs. This is perhaps one reason Robertson-Seymour structural decomposition works: there are few enough remaining graphs for them to have a nice structure.

• Serguei Norine, Paul Seymour, Robin Thomas, and Paul Wollan, Proper minor-closed families are small, Journal of Combinatorial Theory, Series B 96(5) 754–757, 2006. doi:10.1016/j.jctb.2006.01.006 (preprint)

One attempt to go beyond minor-closed classes is via classes defined by forbidden subgraphs or forbidden induced subgraphs.

Graph properties defined by a finite set of forbidden subgraphs or induced subgraphs are decidable in polynomial time, by examining all possible subgraphs.

I find the really interesting case to be hereditary graph properties where the forbidden set is infinite. A hereditary property is closed under taking of induced substructures, or equivalently consists of the $F$-free structures, where $F$ is a set of forbidden induced substructures, not necessarily finite. For $F$-free classes, an infinite set $F$ doesn't lead to a recognition algorithm in any obvious way.

It is also not clear why for some $F$-free graph classes one should be able to find largest independent sets in polynomial time. Trees are the cycle-free graphs; bipartite graphs are the odd-cycle-free graphs; perfect graphs are the (odd-hole,odd-antihole)-free graphs. In each of these cases the forbidden set is infinite yet there is a polynomial-time algorithm to find largest independent sets, and such graphs can also be recognised in polynomial time.

There is only partial progress so far on understanding why some $F$-free classes (with $F$ infinite) are decidable in polynomial time. This progress consists of structural decomposition theorems that lead to polynomial-time recognition algorithms for such classes. Perfect graphs are (odd-hole,odd-antihole)-free, yet can be recognised in polynomial time by the Chudnovsky-Cournéjols-Liu-Seymour-Vušković algorithm. (This remains rather messy after a long period of cleaning.) There are also results if $F$ is the set of all even cycles, or the set of all odd holes, and significant progress has been made on the case where $F$ contains the claw graph.

• Maria Chudnovsky and Paul Seymour, Excluding induced subgraphs, Surveys in Combinatorics 2007, 99–119, Cambridge University Press, ISBN 9780521698238. (preprint)

The hereditary case shares some of the difficulty of the case of minors. For minor-closed graph classes, it is usually not known what the finite set of forbidden minors is, even though it must be finite. For $F$-free graph classes, if the set $F$ is infinite then the class might be nice or it might not be, and we currently have no way to tell other than to try to understand the decomposition structure of the $F$-free graphs.

Answer 3

There is a large and still growing body of theory about classes of fixed-template constraint satisfaction problems that have polynomial-time algorithms. Much of this work requires mastery of the Hobby and MacKenzie book, but luckily for those of us who are more interested in computer science than universal algebra, some parts of this theory have now been simplified enough to be accessible to a TCS audience.

Each of these problems is associated with a set of relations $\Gamma$, and can be expressed as: given a source relational structure $S$ and a target relational structure $T$ with relations from $\Gamma$, does there exist a relational structure homomorphism from $S$ to $T$?

An NP-hard example is when $\Gamma$ is the set containing the relation formed by the back-and-forth directed edges of a complete graph with at least $k \ge 3$ vertices: this expresses Graph $k$-Colouring. An example in P is when every relation in $\Gamma$ contains the tuple $(0,0,\dots,0)$: in this case mapping every element of $S$ to $0$ in $T$ is a (trivial) solution.

It is believed that there is a dichotomy for these problems, which can be expressed roughly as: the problem for $\Gamma$ is in P precisely when the algebra associated with $\Gamma$ has a Taylor term (note that I am leaving out some crucial conditions for the sake of exposition). This extends Schaefer's Dichotomy theorem to the case where the set used to construct the relations in $\Gamma$ contains more than two elements but is still finite. The dichotomy is known to hold for the important case where the relations in $\Gamma$ are conservative; this means in practice that the class of problems contains all the successively simpler subproblems considered by a constraint solver, so the process of constraint solving avoids generating "hard" intermediate instances while solving "easy" problems.

In one important case that falls into P, methods that are similar to Gaussian elimination can be applied. This works if $\Gamma$ is obtained from a system of linear equations over a finite field. More surprising, this also works for a range of problems that do not appear at first glance to have anything to do with linear algebra. They all rely on the relations in $\Gamma$ being closed under "nice" polymorphisms. These are functions that are applied componentwise to collections of tuples from the relation to yield another tuple, which then has to be in the relation. Examples of "nice" polymorphisms are Taylor or cyclic terms.

The results to date seem to indicate that there should be a kind of general powering transformation of an underlying reachability state space that can turn such problems into ones with a constant tuple in each relation, like the example above. (This is my personal interpretation of ongoing research and may well be completely wrong, depending on how the ongoing search for an algorithm for algebras with cyclic terms pans out, so I reserve the right to recant this.) It is known that when there isn't such a transformation then the problem is NP-complete. The frontier of the dichotomy conjecture currently involves closing this gap; see the open problems list from the 2011 Workshop on Algebra and CSPs.

In either case, this probably deserves an entry in Scott's list.

A second class in PTIME allows local consistency techniques to be applied to prune possible solutions, until either a solution is found or no solutions are possible. This is essentially a sophisticated version of the way most people solve Sudoku problems. I don't think this reason currently features in Scott's list either.

It is interesting that Libor Barto's PTIME algorithm for the conservative case in the presence of cyclic terms is nonconstructive: if there is an absorbing subalgebra then there is an algorithm, but no way is known to decide whether a set is an absorbing subalgebra of an algebra. Contrast this with the Robertson-Seymour setup, where there exists an algorithm but it relies on knowing the finite set of forbidden minors, yet no way is known how to decide whether a finite set of graphs is the list of forbidden minors of a graph class. Barto's algorithm relies on knowing the absorbing subuniverses of all subsets of the algebra associated with $\Gamma$, and of the existential nature of the algorithm he says "I love it"...

Finally, there is also much exciting work initiated by Manuel Bodirsky for the case of infinite domains. Some of the algorithms look quite strange and may ultimately turn out to lead to more entries in Scott's list.

Answer 4

Lenstra's integer programming in bounded dimension, the Lenstra-Lenstra-Lovasz algorithm, and related subsequent algorithms - Barvinok's algorithm for the number of integer solutions to an IP problem in bounded dimension and Kannan's P-algorithm for the Frobenius/Sylvester problem can be added as a special category. A notable open problem here is to find a P-algorithm for higher order problems in the Presburger Hierarchy.

Another class of P-algorithm worth mentioning are those P-algorithm given to object proved to exist by randomized proofs. Examples: algorithms for applications of Lovasz-Local Lemma; algorimic versions of Spencer discrepency result; (of slightly different flavour) algorithmic versions of Szemeredi regularity lemma.

Answer 5

I see Chandra alluded to it, but I think structure of an LP relaxation (e.g. due to total unimodularity) is a pervasive form of "structure" that leads to polynomiality. It accounts for a large class of poly time algorithms. If one includes promise problems, it accounts for a large class of approximation algorithms as well. The most frequent classes of reasons one comes across that don't follow from LPs and/or SDPs are Gaussian elimination and dynamic programming.There are of course others such as holographic algorithms that don't have simple explanations.