16
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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 $\endgroup$
    – Alex Meiburg
    Commented Aug 28, 2018 at 20:45
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Aug 28, 2018 at 21:48
  • 2
    $\begingroup$ 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/… ? $\endgroup$
    – Alex Meiburg
    Commented Aug 28, 2018 at 22:36
  • $\begingroup$ Also, it's not at all clear what "feels" exponential to whom. $\endgroup$
    – Raphael
    Commented Sep 3, 2018 at 10:17

2 Answers 2

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ This is a good example! Not having ever really thought about it or needed it, I think I was under the impression that maximal matching on arbitrary graphs was NP-hard. :) $\endgroup$
    – Alex Meiburg
    Commented Aug 29, 2018 at 16:48
5
$\begingroup$

For me all classic and the more recent more efficient algorithms to verify or find a minimum spanning tree (MST) of a connected edge-weighted graph are good candidates. Many of these algorithms are listed in wikipedia.

At the first sight, this problem looks like the travelling salesman problem, one of the few most famous NP-hard problems. Most amazingly, there are linear algorithms to verify an MST and many near-linear algorithms to find an MST! In fact, one of the most famous open problems in algorithms is whether there is a deterministic linear algorithm to find an MST in general graphs. It turns out there are rich math and graph structures and properties as well as a multitude of practical applications that are associated to MST, making it one of the more enjoyable and expandable topics in computer science course. For a slightly outdated but very well-written comprehensive introduction, please check the tutorial by Jason Eisner.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.