# 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 solution to. Repeated squaring or solving 2-SAT is something an undergraduate could possibly come up with on their own, but if you had only learned about NP-Complete problems without having seen HORNSAT, it might sound like a natural candidate for NP-Completeness. Solving the CFSG or having a polynomial way to check for Delta-Wye reducability are no mean feats.

I hope this makes sense; there are obviously lots of subjective attributes here, but I'm curious to hear what other people find to be efficient solutions to "obviously hard" problems.

• As a motivation for this question (because a friend was asking as well): We often talk about how it's important to teach students about NP-Completeness and Undecidability, because it helps them recognize when problems will be Too Hard and they should avoid them. This list would be 'problems you might mistake for NP-Complete but you can actually do'. Not that I expect many students to full under the impression that determinants can't be computed -- just as they likely won't encounter 3SAT in the wild -- but they should recognize other equivalent problems Aug 28 '18 at 20:45
• I suspect this is too broad to be a good fit for our site. Asking for an exhaustive list of something doesn't sound like the kind of question that works well here. "I'm curious to hear what other people find..." sounds like the sort of question that is not suitable here; see our help center.
– D.W.
Aug 28 '18 at 21:48
• I understand, I was trying to acknowledge the subjectivity in this question, but I think this question is largely something people would agree upon and learn from with productive discussion. For questions that have the tone I'm going for maybe (although I know a different site), see cstheory.stackexchange.com/questions/20930/… or cstheory.stackexchange.com/questions/11119/… ? Aug 28 '18 at 22:36
• Also, it's not at all clear what "feels" exponential to whom.
– Raphael
Sep 3 '18 at 10:17