64

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(n6) 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.

Scott Aaronson
  • 13,733
  • 2
  • 62
  • 68
  • 11
    In combinatorial optimization polynomial-time solvability is often closely related to min-max results (related to duality) which establish that the problem is in $NP \cap co-NP$. – Chandra Chekuri Oct 03 '13 at 04:48
  • Chandra: What's a good example of that---one that isn't covered by any of my existing reasons (like convexity)? – Scott Aaronson Oct 03 '13 at 06:01
  • 1
    I would rephrase dynamic programming as divide-and-conquer. That would then cover the case of tree-like structures with bounded width (treewidth, fractional hypertree width, modular width). – András Salamon Oct 03 '13 at 09:43
  • Where does amortized complexity fit in? The common use cases are within P, but I seem to recall reading about exponential-seeming algorithms which are in P using a more careful analysis that takes into account the structure of the computation tree. – András Salamon Oct 03 '13 at 10:00
  • András: Good suggestion re dynamic programming! But regarding amortized complexity, I'd want an example of what you mean before I could comment. – Scott Aaronson Oct 03 '13 at 11:43
  • 1
    IMO BPP is a special case, whose members you have sort of enumerated. I am not aware of a natural problem other than Monte Carlo or polynomial identity testing that is even in BPP but not known to be in P. – S Huntsman Oct 03 '13 at 12:17
  • 2
    If you look at the Schreirer-Sims method, I would argue that this falls into a "linear algebra" like category, as the algorithm closely resembles Gaussian elimination, just with building stabilizing sets. – user834 Oct 03 '13 at 13:36
  • Also, primality testing, both the random and deterministic version, rely on a sort of probabilistic method, so that falls under your first criteria. From what little number theory I've seen, many arguments fall into this sort of probabilistic method/mathematical argument to guarantee polynomial running time. – user834 Oct 03 '13 at 13:45
  • 3
    Scott: convexity by itself is not enough in some sense because the Ellipsoid method shows that one can optimize over convex bodies iff one can separate over it which again is an algorithmic problem! The classic example to keep in mind is the matching algorithm/polytope due to Edmonds. Tutte-Berge formula showed that max-cardinality matching is in $NP \cap co-NP$ before we knew a poly-time algorithm. Same for LP due to duality. – Chandra Chekuri Oct 03 '13 at 14:12
  • 2
    How would you classify fast unification algorithms? (ie, http://en.wikipedia.org/wiki/Unification_%28computer_science%29) People who should know have made analogies to (3) or (7), but I've never seen it spelled out formally. – Neel Krishnaswami Oct 03 '13 at 15:19
  • another apparently broad class, recognition/coloring etc of perfect graphs. where does that fit in? an interesting test/research program to identify an overarching criteria would be to convert problems from the areas known to be in P and then determine if they fit into the categories listed. ie fill a matrix, Does problem in row A overlap with problems in column B. note, there might be a strong case to be made that such a broad classification theory as both sufficient/ necessary is so ambitious it would basically be equivalent to a P≠NP proof.... – vzn Oct 03 '13 at 15:40
  • 1
    @Chandra: Yeah, I know convexity doesn't suffice by itself -- but nevertheless, I tend to lump LP, SDP, and slight generalizations of SDP as "polytime solvable cases of convex programming" -- and if you tell me that there's a simple reduction from your problem to one of those things, then I'd say the fact that your problem is in P has been fully explained. Also, I'm a bit leery of arguments that have since been superseded by better ones. Are there examples of problems that are in P for "duality" reasons, for which we DON'T currently know any other reason why they're in P? – Scott Aaronson Oct 03 '13 at 16:24
  • @vzn: Perfect graphs are a great example! I'll have to think about that one more -- I remember the algorithm was complicated, but I don't remember the details. – Scott Aaronson Oct 03 '13 at 16:26
  • 1
    @Neel: I don't know how nontrivial polynomial-time unification algorithms work. Would anyone who does know care to give a 2-3 sentence summary? – Scott Aaronson Oct 03 '13 at 16:27
  • 4
    I'd say that perfect graphs are a case in point for Chandra's argument. Chromatic number and maximum clique size are dual problems, but in general there is only weak duality. In perfect graphs however we also have strong duality. The reason the Lovasz $\vartheta$ works is that it is a common convex relaxation of both chromatic number and clique number, so if there is no gap between these two, then there is no gap between them and $\vartheta$. IMO, duality is the best explanation why bipartite matching and min s-t cut work as well: the classic algorithms for both are sort of primal-dual. – Sasho Nikolov Oct 03 '13 at 17:02
  • is there a paper that outlines/surveys the property chandra/SN refer to, "In combinatorial optimization polynomial-time solvability is often closely related to min-max results (related to duality)"...? is it duality/optimization? – vzn Oct 03 '13 at 17:15
  • 2
    About terminology, I agree with Andras that DP probably should be renamed divide and conquer, or "recursive characterization". This then captures a lot of cases. Also (1) is a bit too vague I think, but your explanation suggests you mean problems whose solution is witnessed by a constant-size substructure (so all kinds of algorithms based on excluded minor characterizations). – Sasho Nikolov Oct 03 '13 at 17:18
  • 8
    I would add submodularity to that list. Whereas some results involving maximization or minimization of submodular functions are related to matroids or convexity, I don't think that connection is strong enough to explain most algorithmic results involving submodularity. – sd234 Oct 03 '13 at 18:05
  • 2
    @Scott: What I am trying to say regarding LP is the following. Optimization over implicitly defined polytopes (with exponential number of constraints) can be solved efficiently in some cases and not in some other cases. Regarding weighted matching for instance. There is no compact LP that captures this problem so far which means we cannot simply reduce it to LP. – Chandra Chekuri Oct 03 '13 at 19:23
  • 7
    How does an O(n^6) planarity algorithm follow from Kuratowski's theorem? –  Oct 03 '13 at 20:21
  • 2
    To avoid confusion, I'd probably separate matroid/greedy and matching in the list. – Gil Kalai Oct 03 '13 at 21:04
  • I am surprised that the physicist didn't want to know about the "usual suspects" when we try to put a problem in BQP as well. Well, perhaps the list wouldn't be much bigger than this one after all. – Alessandro Cosentino Oct 04 '13 at 03:51
  • 1
    @Alessandro: The whole context for the discussion was about putting quantum simulation problems---i.e., things already known to be in BQP---into P or BPP. – Scott Aaronson Oct 04 '13 at 07:14
  • 1
    @planar: I thought an $O(n^3)$ algorithm for planarity checking follows from Wagner's result that planar = $(K_{3,3},K_5)$-minor-free and the cubic Robertson-Seymour algorithm to check if a graph contains another as a minor? (Agreed this is not really via Kuratowski.) – András Salamon Oct 04 '13 at 13:04
  • 1
    Although I generally agree about "linear algebra" as a category, I think that computing the determinant and solving a linear system should be separate from finding eigenvalues. Finding eigenvalues is equivalent to finding roots of univariate polynomials, and the algorithms for that (Berlekamp randomized over finite fields, Neff-Reif for approximating eigenvalues to arbitrary precision over R or C) are of a very different flavor than computing det or solving a linear system, for which there are many known efficient (and even ring-independent) algorithms. – Joshua Grochow Oct 06 '13 at 01:56
  • 1
    @SHuntsman: My answer to http://cstheory.stackexchange.com/questions/11425/problem-in-bpp-but-not-known-to-be-in-rp-or-co-rp contains a natural problem known to be in BPP, but not known to be in RP nor coRP. The "reason" it's in BPP is based on very nontrivial mathematical results on finite (simple) groups, rather than PIT or MCMC. – Joshua Grochow Oct 06 '13 at 01:58
  • 1
    Per the now-answered MathOverflow question '**What is the "tangle" at the heart of quantum simulation?', one emerging answer is that the singularity structure of low-dimension projective varietal state-spaces is compatible with flow-induced symplectic isomorphisms that are not metric isomorphisms. The practical consequence is that the computational advantages of group-representation methods in quantum simulations naturally extend to thermodynamic classes of Hamiltonian interactions. – John Sidles Oct 07 '13 at 11:08
  • 1
    fyi boaz barak wrote up some similar ideas Structure vs. Combinatorics in Computational Complexity – vzn Oct 15 '13 at 20:11
  • In a way, if there is polynomial-time solution, then there is always a dynamic programming method since running a fixed TM on some input for some polynomial number of steps is a typical example of dynamic programming. – phs Oct 15 '13 at 15:04
  • Why do you say that running a TM for poly-bounded number of steps is an instance of dynamic programming? I'm failing to make the conceptual leap. – András Salamon Oct 15 '13 at 15:15
  • 1
    @AndrásSalamon: This is an issue that comes up when one tries to formalize what one means by "dynamic programming." If you say it's "A poly-size table that is filled in locally," then you can treat the blank computation history of a TM as such a table, which can then be filled in locally by simulating the TM. – Joshua Grochow Oct 15 '13 at 15:48
  • Yes, a poly-size table that is filled in locally. Thanks Joshua. I should have said that running a TM "can be seen as dynamic programming", not "is a typical(??) example". – phs Oct 15 '13 at 19:32

5 Answers5

20

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.

András Salamon
  • 19,000
  • 3
  • 64
  • 150
  • do those refs capture the reduction to the "nice semidefinite programming formulations"? but only some SDP problems are in P, right? – vzn Oct 03 '13 at 17:09
  • The link with semidefinite programming (and the proof that largest independent sets can be found in perfect graphs in polynomial time) was made in the original 1981 paper of Grötschel/Lovász/Schrijver (section 6), see http://dx.doi.org/10.1007/BF02579273 while the refs above deal with the link with CSP. – András Salamon Oct 03 '13 at 20:55
  • 1
    Another important example is that of graphs with forbidden subgraphs where Roberson-Seymour theory allows P-time algorithm for various algorithmic questions. (Often with huge constants.) P-algorithm for perfect graphs and graph with forbidden induced subgraphs go beyond the applications of LP and PSD programming. – Gil Kalai Oct 03 '13 at 21:20
  • @Gil: thanks, I have tried to address this comment in an edit. Perhaps you could expand on the SDP connection separately? – András Salamon Oct 04 '13 at 12:59
  • 1
    A result that is interesting and similar to the forbidden minors theory is Seymour's characterization of totally unimodular matrices. These are equivalent to regular matroids, and Seymour's theorem says that they can be "built up" from (co-)graphic matroids and 5 special matroids using simple compositions operations. The compositions are also easy to "undo" which leads to a totally non-obvious recognition algorithm for total unimodularity. As @Kunal mentioned, total unimodularity itself explains the polytme solvability of a lot of problems. – Sasho Nikolov Oct 04 '13 at 21:37
20

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.

Paul Beame
  • 641
  • 4
  • 5
15

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.

Gil Kalai
  • 6,033
  • 35
  • 73
15

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.

András Salamon
  • 19,000
  • 3
  • 64
  • 150
12

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.

Kunal
  • 304
  • 1
  • 5