<p>Some graph classes allow polynomial-time algorithms for problems that are NP-hard for the class of <em>all</em> 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).</p>

<p>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.</p>

<ul>
<li><p>András Z. Salamon and Peter G. Jeavons, <em>Perfect constraints are tractable</em>,
CP 2008,
LNCS 5202,
524–528.
doi:<a href="http://dx.doi.org/10.1007/978-3-540-85958-1_35">10.1007/978-3-540-85958-1_35</a></p></li>
<li><p>Meinolf Sellmann, 
<em>The Polytope of Tree-Structured Binary Constraint Satisfaction Problems</em>,
CPAIOR 2008,
LNCS 5015,
367–371.
doi:<a href="http://dx.doi.org/10.1007/978-3-540-68155-7_39">10.1007/978-3-540-68155-7_39</a></p></li>
</ul>

<hr>

<p>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 <a href="https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem">Robertson-Seymour theorem</a>).  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.</p>

<ul>
<li>Neil Robertson and P. D. Seymour, <em>Graph Minors. XIII. The disjoint paths problem</em>, Journal of Combinatorial Theory, Series B <strong>63</strong>(1) 65–110, 1995.  doi:<a href="http://dx.doi.org/10.1006/jctb.1995.1006">10.1006/jctb.1995.1006</a></li>
</ul>

<p>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.</p>

<ul>
<li>Serguei Norine, Paul Seymour, Robin Thomas, and Paul Wollan, <em>Proper minor-closed families are small</em>, Journal of Combinatorial Theory, Series B <strong>96</strong>(5) 754–757, 2006.
doi:<a href="http://dx.doi.org/10.1016/j.jctb.2006.01.006">10.1016/j.jctb.2006.01.006</a> (<a href="http://www.math.princeton.edu/~snorin/papers/smallfam.pdf">preprint</a>)</li>
</ul>

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

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

<p>I find the really interesting case to be hereditary graph properties where the forbidden set is <em>infinite</em>.  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.</p>

<p>It is also not clear why for some $F$-free graph classes one should be able to find largest independent sets in polynomial time.  <a href="http://graphclasses.org/classes/gc_342.html">Trees</a> are the cycle-free graphs; <a href="http://graphclasses.org/classes/gc_69.html">bipartite graphs</a> are the odd-cycle-free graphs; <a href="http://graphclasses.org/classes/gc_56.html">perfect graphs</a> 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.</p>

<p>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 <a href="http://dx.doi.org/10.1007/s00493-005-0012-8">Chudnovsky-Cournéjols-Liu-Seymour-Vušković algorithm</a>.  (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.</p>

<ul>
<li>Maria Chudnovsky and Paul Seymour, <em>Excluding induced subgraphs</em>, Surveys in Combinatorics 2007, 99–119, Cambridge University Press, ISBN 9780521698238. (<a href="http://www.columbia.edu/~mc2775/induced_survey.pdf">preprint</a>)</li>
</ul>

<p>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.</p>

CC BY-SA 3.0
2013-10-03T17:09:28.157Z
do those refs capture the reduction to the "nice semidefinite programming formulations"? but only some [SDP problems](http://en.wikipedia.org/wiki/Semidefinite_programming) are in P, right?
vzn
CC BY-SA 3.0
2013-10-03T20:55:08.320Z
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
CC BY-SA 3.0
2013-10-03T21:20:02.560Z
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
CC BY-SA 3.0
2013-10-04T12:59:10.860Z
@Gil: thanks, I have tried to address this comment in an edit.  Perhaps you could expand on the SDP connection separately?
András Salamon
CC BY-SA 3.0
2013-10-04T21:37:33.640Z
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
CC BY-SA 3.0
2013-10-03T16:38:44.653Z
2013-10-04T10:45:12.787Z
2013-10-04T10:45:12.787Z
András Salamon
<p>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.</p>

CC BY-SA 3.0
2013-10-04T16:24:04.830Z
I would argue that LLL (and PSLQ/HJLS) are _generalizations_ of the GCD algorithm, rather than the other way around.
user834
CC BY-SA 3.0
2013-10-04T19:11:31.697Z
@user834: "you can view the Euclidean algorithm as a special case" $\equiv$ "LLL (and PSLQ/HJLS) are generalizations of the GCD algorithm"?
András Salamon
CC BY-SA 3.0
2013-10-04T23:45:16.297Z
What are PSLQ/HJLS ?
Gil Kalai
CC BY-SA 3.0
2013-10-06T01:35:20.983Z
The [Partial Sum LQ (as in factorization) algorithm](http://mathworld.wolfram.com/PSLQAlgorithm.html) and [Hastad, Just, Lagarias and Schnorr algorithm](http://mathworld.wolfram.com/HJLSAlgorithm.html) (I assume the algorithm was named after the author's last names) are more "modern" algorithms for integer relation detection.
user834
CC BY-SA 3.0
2013-10-03T20:30:15.887Z
2013-10-03T20:30:15.887Z
Paul Beame
<p>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.</p>

CC BY-SA 3.0
2013-10-04T00:32:33.473Z
2013-10-04T00:32:33.473Z
Kunal
<p>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 <a href="http://www.ams.org/books/conm/076/">Hobby and MacKenzie book</a>, 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.</p>

<p>Each of these problems is associated with a set of relations $\Gamma$, and can be expressed as: <em>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$?</em></p>

<p>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.</p>

<p>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 <a href="https://en.wikipedia.org/wiki/Schaefer%27s_dichotomy_theorem">Schaefer's Dichotomy theorem</a> 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 <em>conservative</em>; 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.</p>

<p>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.</p>

<p>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 <em>and may well be completely wrong</em>, 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 <em>isn't</em> such a transformation then the problem is NP-complete.  The frontier of the dichotomy conjecture currently involves closing this gap; see the <a href="http://www.karlin.mff.cuni.cz/~barto/Articles/fields-2011-problems.pdf">open problems list from the 2011 Workshop on Algebra and CSPs</a>.</p>

<p>In either case, this probably deserves an entry in Scott's list.</p>

<p>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.</p>

<p>It is interesting that <a href="http://www.karlin.mff.cuni.cz/~barto/research.html">Libor Barto</a>'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 <a href="http://www.karlin.mff.cuni.cz/~barto/Articles/Barto_LICS.pdf">he says</a> "I love it"...</p>

<p>Finally, there is also much exciting work initiated by <a href="http://www.lix.polytechnique.fr/~bodirsky/publications.html">Manuel Bodirsky</a> 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.</p>

CC BY-SA 3.0
2013-10-04T16:27:04.630Z
2013-10-04T16:48:21.380Z
2013-10-04T16:48:21.380Z
András Salamon
<p>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.</p>

<p>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. </p>

CC BY-SA 3.0
2013-10-03T20:04:12.563Z
2013-10-08T05:46:04.237Z
2013-10-08T05:46:04.237Z
Gil Kalai
<p>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:</p>

<p>(0) <b>Mathematical characterization.</b> 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.  <strike>Example: graph planarity, for which an O(n<sup>6</sup>) algorithm follows from Kuratowski's theorem.</strike></p>

<p>(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.)</p>

<p>Anyway, this is specifically <i>not</i> the sort of situation that most interests me.</p>

<p>(1) <b>Dynamic programming.</b>  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.</p>

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

<p>(3) <b>Linear algebra.</b>  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.</p>

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

<p>(5) <b>Polynomial identity testing.</b>  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.</p>

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

<p>(7) <b>Euclidean algorithm.</b>  GCD, continued fractions...</p>

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

<p>My question is: <b>what are the most important things I've left out?</b></p>

<p>To clarify:</p>

<ul>
<li><p>I realize that no list can possibly be complete: whatever finite number of reasons you give, <i>someone</i> 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.</p></li>
<li><p>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.</p></li>
</ul>

<p>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 <i>don't</i> fit into the above list -- or other ideas for improving my crude first attempt to make good on my boast to the physicist.</p>

CC BY-SA 3.0
2013-10-03T04:48:20.403Z
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
CC BY-SA 3.0
2013-10-03T06:01:07.893Z
Chandra: What's a good example of that---one that isn't covered by any of my existing reasons (like convexity)?
Scott Aaronson
CC BY-SA 3.0
2013-10-03T09:43:40.123Z
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
CC BY-SA 3.0
2013-10-03T10:00:27.007Z
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
CC BY-SA 3.0
2013-10-03T11:43:01.827Z
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
CC BY-SA 3.0
2013-10-03T12:17:02.383Z
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
CC BY-SA 3.0
2013-10-03T13:36:09.840Z
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
CC BY-SA 3.0
2013-10-03T13:45:44.007Z
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
CC BY-SA 3.0
2013-10-03T14:12:26.733Z
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
CC BY-SA 3.0
2013-10-03T15:19:56.913Z
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
CC BY-SA 3.0
2013-10-03T15:40:42.020Z
another apparently broad class, recognition/coloring etc of [perfect graphs](http://en.wikipedia.org/wiki/Perfect_graph). 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
CC BY-SA 3.0
2013-10-03T16:24:19.460Z
@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
CC BY-SA 3.0
2013-10-03T16:26:31.187Z
@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
CC BY-SA 3.0
2013-10-03T16:27:30.317Z
@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
CC BY-SA 3.0
2013-10-03T17:02:44.010Z
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
CC BY-SA 3.0
2013-10-03T17:15:39.410Z
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](http://en.wikipedia.org/wiki/Duality_(optimization))?
vzn
CC BY-SA 3.0
2013-10-03T17:18:42.037Z
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
CC BY-SA 3.0
2013-10-03T18:05:39.890Z
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
CC BY-SA 3.0
2013-10-03T19:23:57.000Z
@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
CC BY-SA 3.0
2013-10-03T21:04:37.423Z
To avoid confusion,  I'd probably separate matroid/greedy and matching in the list.
Gil Kalai
CC BY-SA 3.0
2013-10-04T03:51:10.903Z
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
CC BY-SA 3.0
2013-10-04T07:14:31.650Z
@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
CC BY-SA 3.0
2013-10-04T13:04:19.667Z
@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
CC BY-SA 3.0
2013-10-06T01:56:27.643Z
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
CC BY-SA 3.0
2013-10-06T01:58:46.323Z
@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
CC BY-SA 3.0
2013-10-07T11:08:07.723Z
Per the now-answered *MathOverflow* question '[**What is the "tangle" at the heart of quantum simulation?](http://mathoverflow.net/questions/142997/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
CC BY-SA 3.0
2013-10-15T15:04:02.823Z
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
CC BY-SA 3.0
2013-10-15T15:15:06.270Z
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
CC BY-SA 3.0
2013-10-15T15:48:45.910Z
@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
CC BY-SA 3.0
2013-10-15T19:32:45.973Z
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
CC BY-SA 3.0
2013-10-15T20:11:43.560Z
fyi boaz barak wrote up some similar ideas [Structure vs. Combinatorics in Computational Complexity](http://www.boazbarak.org/Papers/meta-alg.pdf)
vzn
<big-list><big-picture>
Overarching reasons why problems are in P or BPP
Scott Aaronson
# Overarching reasons why problems are in P or BPP

(Asked by: username_0 on 2013-10-03)

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.

**Tags:** big-list, big-picture
> **Comments:**
> **username_1**: 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$.  
> **username_0**: Chandra: What's a good example of that---one that isn't covered by any of my existing reasons (like convexity)?  
> **username_2**: 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).  
> **username_2**: 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.  
> **username_0**: András: Good suggestion re dynamic programming!  But regarding amortized complexity, I'd want an example of what you mean before I could comment.  
> **username_3**: 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.  
> **username_4**: 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.  
> **username_4**: 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.  
> **username_1**: 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.  
> **username_5**: 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.  
> **username_6**: another apparently broad class, recognition/coloring etc of [perfect graphs](http://en.wikipedia.org/wiki/Perfect_graph). 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....  
> **username_0**: @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?  
> **username_0**: @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.  
> **username_0**: @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?  
> **username_7**: 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.  
> **username_6**: 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](http://en.wikipedia.org/wiki/Duality_(optimization))?  
> **username_7**: 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).  
> **username_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.  
> **username_1**: @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.  
> **username_9**: To avoid confusion,  I'd probably separate matroid/greedy and matching in the list.  
> **username_10**: 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.  
> **username_0**: @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.  
> **username_2**: @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.)  
> **username_11**: 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.  
> **username_11**: @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.  
> **username_12**: Per the now-answered *MathOverflow* question '[**What is the "tangle" at the heart of quantum simulation?](http://mathoverflow.net/questions/142997/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.  
> **username_13**: 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.  
> **username_2**: 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.  
> **username_11**: @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.  
> **username_13**: 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".  
> **username_6**: fyi boaz barak wrote up some similar ideas [Structure vs. Combinatorics in Computational Complexity](http://www.boazbarak.org/Papers/meta-alg.pdf)  

---

## 5 answers

### Answer by username_2 on 2013-10-03. Score: 21

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](http://dx.doi.org/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](http://dx.doi.org/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](https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_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](http://dx.doi.org/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](http://dx.doi.org/10.1016/j.jctb.2006.01.006) ([preprint](http://www.math.princeton.edu/~snorin/papers/smallfam.pdf))

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](http://graphclasses.org/classes/gc_342.html) are the cycle-free graphs; [bipartite graphs](http://graphclasses.org/classes/gc_69.html) are the odd-cycle-free graphs; [perfect graphs](http://graphclasses.org/classes/gc_56.html) 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](http://dx.doi.org/10.1007/s00493-005-0012-8). (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](http://www.columbia.edu/~mc2775/induced_survey.pdf))

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.

> **Comments:**
> **username_6**: do those refs capture the reduction to the "nice semidefinite programming formulations"? but only some [SDP problems](http://en.wikipedia.org/wiki/Semidefinite_programming) are in P, right?  
> **username_2**: 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.  
> **username_9**: 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.  
> **username_2**: @Gil: thanks, I have tried to address this comment in an edit.  Perhaps you could expand on the SDP connection separately?  
> **username_7**: 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.  

---

### Answer by username_14 on 2013-10-03. Score: 21

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.

> **Comments:**
> **username_4**: I would argue that LLL (and PSLQ/HJLS) are _generalizations_ of the GCD algorithm, rather than the other way around.  
> **username_2**: @user834: "you can view the Euclidean algorithm as a special case" $\equiv$ "LLL (and PSLQ/HJLS) are generalizations of the GCD algorithm"?  
> **username_9**: What are PSLQ/HJLS ?  
> **username_4**: The [Partial Sum LQ (as in factorization) algorithm](http://mathworld.wolfram.com/PSLQAlgorithm.html) and [Hastad, Just, Lagarias and Schnorr algorithm](http://mathworld.wolfram.com/HJLSAlgorithm.html) (I assume the algorithm was named after the author's last names) are more "modern" algorithms for integer relation detection.  

---

### Answer by username_2 on 2013-10-04. Score: 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](http://www.ams.org/books/conm/076/), 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](https://en.wikipedia.org/wiki/Schaefer%27s_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](http://www.karlin.mff.cuni.cz/~barto/Articles/fields-2011-problems.pdf).

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](http://www.karlin.mff.cuni.cz/~barto/research.html)'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](http://www.karlin.mff.cuni.cz/~barto/Articles/Barto_LICS.pdf) "I love it"...

Finally, there is also much exciting work initiated by [Manuel Bodirsky](http://www.lix.polytechnique.fr/~bodirsky/publications.html) 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 by username_9 on 2013-10-03. Score: 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.


---

### Answer by username_15 on 2013-10-04. Score: 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.


---

