19

Recently, I went through the painful fun experience of informally explaining the concept of computational complexity to a young talented self-taught programmer, who never took a formal course in algorithms or complexity before. Not surprisingly, a lot of notions seemed strange at first but made sense with some examples (PTIME, intractability, uncomputability), while others seem to come more natural (problem classification via reductions, time and space as resources, asymptotic analysis). Everything was going great until I accidentally admitted that SAT can be solved efficiently* in practice... And just like that, I lost them. It didn't matter how convincingly I was trying to argue for theory, the kid was convinced that it was all artificial crap math that he should not care for. Well...

¯\_(ツ)_/¯

No, I was not heart-broken, nor did I really care about what he thought, that's not the point of this question. Our conversation had me thinking of a different question,

How much do I really know about problems that are theoretically intractable (superpolynomial time complexity) but practically solvable (via heuristics, approximations, SAT-solvers etc.)?

I realized, not much. I know that there are some very efficient SAT-solvers that solve enormous instances efficiently, that Simplex works great in practice, and maybe a few more problems or algorithms. Can you help me paint a more complete picture? Which well-known problems or even classes of problems are in this category?

TL;DR: What are problems that are counter-intuitively solvable in practice? Is there an (updated) resource to read more? Do we have a characterization for them? And, finally, as a general discussion question, shouldn't we?

EDIT #1: In trying to answer my last discussion question about such a characterization, I was introduced to smoothed analysis of algorithms, a concept introduced by Daniel Spielman and Shang-Hua Teng in [1] that continuously interpolates between the worst-case and average-case analyses of algorithms. It is not exactly the characterization discussed above, but it captures the same concept, and I found it interesting.

[1] Spielman, Daniel A., and Shang-Hua Teng. "Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time." Journal of the ACM (JACM) 51, no. 3 (2004): 385-463.

Konstantinos Koiliaris
  • 836
  • 1
  • 8
  • 17
  • 6
    What did you mean by stating that SAT can be efficiently solved in practice? Why does your friend rely on security on the Internet? Presumably there are no hard problems in practice? Robustness is one of the main advantage of poly-time/efficient solvability. – Chandra Chekuri May 21 '18 at 03:24
  • 6
    Graph isomorphism is a natural candidate. – D.W. May 21 '18 at 04:11
  • 2
    Hey, @ChandraChekuri, what I meant was that practically SAT-solvers can answer SAT instances with millions of variables and clauses. Or at least, that's what I thought was the case. I am not sure I understand what you mean about "security on the Internet"? I am not arguing against the formalism, I am interested in problems that are in theory intractable, but for all practical purposes (maybe due to a decent approximation, maybe due to the special structure of real-world instances, etc.) are considered "tractable". – Konstantinos Koiliaris May 21 '18 at 17:00
  • 1
    @KonstantinosKoiliaris I think the point was that the security of all kinds of cryptographic protocols relies on $P\ne NP$ (usually even something much stronger), and as such provides plentiful examples of problems from routine practice that are extremely hard for SAT-solvers (or we very much hope so, anyway). – Emil Jeřábek May 22 '18 at 07:49
  • @EmilJeřábek that makes sense, thanks for clarifying. I did not mean to make it sound like all instances of SAT are easy for solvers. – Konstantinos Koiliaris May 22 '18 at 20:04
  • Most program analysis questions are undecidable [Rice], but many program analyzers are pretty fast. That's, of course, because humans write simple programs, mostly. – Radu GRIGore May 23 '18 at 05:05
  • 2
    In this vein, it might be good to check out Generic complexity. In fact, it turns out that the halting problem is almost always solvable in polynomial time, as is, for example, SAT (in fact, SAT has a stronger guarantee). What is meant by “almost always” is that the problem admits an algorithm such that the proportion of inputs for which the algorithm halts (and outputs the correct answer, of course) in polynomial time goes to 1 as the length of the input increases. – Guillermo Angeris May 23 '18 at 07:53

4 Answers4

16

  • Highly structured SAT instances (even on millions of variables) can often be solved in practice. However, random SAT instances near the satisfiability threshold with even a few hundred variables are still open (meaning, even in practice, if you generate such a thing you may never know in the lifetime of the universe whether the thing you generated is satisfiable or not using current SAT solvers). You might be interested in this related question and its answers.

  • Clique finders are also shockingly good "in practice"

  • Integer programming and mixed integer-linear programming (with some rational and some integer variables) are the focus of whole Operations Research departments, and can often (but not always) be solved in practice

  • From what I understand, many $\mathsf{PSPACE}$-complete problems that arise in verification can often be solved in practice, but "in practice" usually implies "on highly structured instances". (In contrast, we still don't know who wins for pretty small instances of the game of Go, which is another $\mathsf{PSPACE}$-complete problem.)

  • Many problems in computational algebraic geometry can be solved in practice on small instances using Grobner bases, but these fail miserably on larger instances, or even small instances that have high "complexity" (as measured by the Castelnuovo-Mumford regularity). And these problems are even $\mathsf{EXPSPACE}$-complete!

  • As already pointed out in the comments by D. W., Graph Isomorphism can pretty much be solved in practice. It is very hard to stump modern GI software such as nauty, bliss, saucy, etc.

Renato
  • 3
  • 1
Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228
  • Thanks Joshua, I am giving it to you for the most interesting / broad problems suggested. – Konstantinos Koiliaris May 25 '18 at 06:14
  • 1
    Clique finders are not always good in practice. It really depends on the graph. And your link seems to be talking only about random graphs. – Peter Shor May 28 '18 at 17:16
  • Expanding a bit about GI: AFAIK most state-of-the-art GI solvers such as the ones mentioned use a optimized individualization-refinement approach (where the refinement is color refinement, which already works as a quasilinear GI test for almost all graphs), but Neuen and Schweitzer recently showed exponential lower bounds for this method and constructed (practically) hard instances. – Watercrystal Jun 02 '18 at 23:11
  • @Watercrystal: I take "in practice" to mean both "in real code" and "on instances that arose because someone actually wanted to know the answer". While the results you cite are indeed interesting, I don't think their instances pass the second criterion. For instances that people actually want to solve, the existing solvers seem to do very well. – Joshua Grochow Jun 03 '18 at 05:33
  • @PeterShor: won't that be true of almost any answer to this question? Also, while I definitely agree that it depends on the instance, do you know of a natural source of instances that people want to know the answer to but which stump modern clique finders? I'd be very interested to know. (I have a better sense of this sort of thing for SAT, but less of a good sense of the landscape of clique instances, so it's always good to know of more.) (FWIW, that wasn't my link - it got edited in; I know that random instances are often not like "real-world" ones.) – Joshua Grochow Jun 03 '18 at 05:36
  • 1
    @JoshuaGrochow: Yes, I agree with you on this. I just wanted to expand on the "counter-intuitive" part of the question as OP specifically mentioned that Simplex performs very well in practice even though exponential lower bounds are known and we have the same situation here. – Watercrystal Jun 03 '18 at 11:45
  • 1
    I just have experience with Keller's conjecture, where the (admittedly large) graphs stumped many clique-finding algorithms. – Peter Shor Jun 03 '18 at 12:42
13

The Hindley-Milner type system is used in functional programming languages (Haskell, SML, OCaml). The type-inference algorithm is nearly linear in practice and works amazingly well, but is known to be DEXPTIME-complete!

A general comment: it is no surprise that worst-time complexity is not necessarily a very good measure of the practical performance on an algorithm. However, to say that the discrepancy between theory and practice makes complexity theory useless is like saying that natural numbers are a waste because we only use a miniscule amount of all the numbers available. A famous philosopher once said that "Experience without theory is blind, but theory without experience is mere intellectual play."

Andrej Bauer
  • 28,823
  • 1
  • 80
  • 133
5

More examples, mostly from programming languages:

  1. k-CFA (k-Control Flow Analysis) is EXPTIME-complete (Van Horn & Mairson 2008), but whole-program optimizing compilers like MLton perform it anyway. The compile times are long, but rarely disastrous.
  2. Resolving (dynamic) overloading is generally NP-complete (Palsberg 2012). But then it is rarely a problem in the real world.
  3. Register allocation is polynomially-reducible to k-graph coloring (where $k$ is the number of registers), which is NP-complete. But again it is rarely a problem in the real world.
  4. SMT solving is generally NP-complete, but commercial SMT solvers (like Z3 and CVC4) are usually pretty performant. I don't work directly with SMT solvers, but I've used Z3 indirectly from Liquid Haskell and Dafny, and the checking times seem OK.
  5. The decision problem for Presburger arithmetic is really complex (Fischer & Rabin 1974), but Bill Pugh's decision algorithm, the Omega test (Pugh 1991), runs generally within low-order polynomial-time.

Remember that big-$O$ (and thus complexity classes) is about asymptotic behavior, i.e., when $n$ grows. However, in many real-world problems, $n$ is usually small. Moreover, these cases usually don't induce worst-case behavior. To get worst-case behavior in Hindley-Damas-Milner, for example, you would need to write some pretty bad code.

References:

[1] David Van Horn and Harry G. Mairson. 2008. Deciding kCFA is complete for EXPTIME. In Proceedings of the 13th ACM SIGPLAN International Conference on Functional Programming (ICFP '08). ACM, New York, NY, USA, 275-282.

[2] http://web.cs.ucla.edu/~palsberg/paper/dedicated-to-kozen12.pdf

[3] M. J. Fischer and M. O. Rabin. 1974. SUPER-EXPONENTIAL COMPLEXITY of PRESBURGER ARITHMETIC. Technical Report. Massachusetts Institute of Technology, Cambridge, MA, USA.

[4] William Pugh. 1991. The Omega test: a fast and practical integer programming algorithm for dependence analysis. In Proceedings of the 1991 ACM/IEEE Conference on Supercomputing (Supercomputing '91). ACM, New York, NY, USA, 4-13.

xrq
  • 1,175
  • 6
  • 17
1

training neural networks using gradient descent methods is also proven to be badly np-hard problem https://www.cs.utexas.edu/~klivans/crypto-hs.pdf but are generally solvable in practice.

thecomplexitytheorist
  • 141
  • 4