Problems that feel exponential but are P

I'm trying to build a list of algorithms/problems that are "exceptionally useful", as in, solving problems that 'seem' very exponential in nature, but have some particularly clever algorithm that ultimately solves them. Examples of what I mean:

• Linear Programming (The simplex algorithm is exponential time; it took a long time to find a polynomial time solution!)

• More generally, Semidefinite Programming

• Primality testing

• 2-SAT and HORNSAT

• Computing determinants (if this doesn't sound difficult, consider the permanent)

• Finding perfect matchings

• A variety of hard group theoretic problems that can be accomplished using the Classification of Finite Simple Groups

• A variety of hard graph problems that can be accomplished using complicated Forbidden Minor characterizations (embeddability on an arbitrary surface; bounding of treewidth and branchwidth; Delta-Wye reducible graphs)

• Computing exponentials in a bounded group (i.e. computing $a^b \mod k$ in $\log b$ steps, as accomplished by repeated squaring)

• Computations relying on the LLL algorithm. (As a special case: Euclidean algorithm. As a more general case: PSLQ or HJLS algorithms.)

• Constraint problems without Taylor terms (?). I admit I don't fully understand this, but it sounds like it probably subsumes the 2-SAT / HORNSAT cases above, and any linear algebra over finite fields. See here for a longer post

• Problems computable via holographic reductions.

As a honorable mention, I would also mention Graph Isomorphism, because it's still awfully easy ($n^{\log^2 n}$), and equivalent to so many other isomorphism problems:

• Digraphs/multigraphs/hypergraphs (a sort of 'harder' problem)

• Finite automata/CFGs

Obviously there's a range of difficulty in these, but all leave at least some people with some sense of 'surprise' in the sense that the problem can sound difficult but turn out tractable. LP might sound relatively straightforward, but took people quite a while to build an actual sol

For me one of the most efficient algorithms is the Blossom V algorithm that finds maximum weight perfect matching in a general graph:

https://en.m.wikipedia.org/wiki/Blossom_algorithm

StackExchange Computer Science Q#96721, answer score: 6