19
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 6
    $\begingroup$ 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. $\endgroup$
    – Chandra Chekuri
    May 21, 2018 at 3:24
  • 6
    $\begingroup$ Graph isomorphism is a natural candidate. $\endgroup$
    – D.W.
    May 21, 2018 at 4:11
  • 2
    $\begingroup$ 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". $\endgroup$
    – Konstantinos Koiliaris
    May 21, 2018 at 17:00
  • 1
    $\begingroup$ @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). $\endgroup$
    – Emil Jeřábek
    May 22, 2018 at 7:49
  • 2
    $\begingroup$ 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. $\endgroup$
    – Guillermo Angeris
    May 23, 2018 at 7:53

4 Answers 4

Reset to default
16
$\begingroup$

  • 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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thanks Joshua, I am giving it to you for the most interesting / broad problems suggested. $\endgroup$
    – Konstantinos Koiliaris
    May 25, 2018 at 6:14
  • 1
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    May 28, 2018 at 17:16
  • $\begingroup$ 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. $\endgroup$
    – Watercrystal
    Jun 2, 2018 at 23:11
  • 1
    $\begingroup$ @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. $\endgroup$
    – Watercrystal
    Jun 3, 2018 at 11:45
  • 1
    $\begingroup$ I just have experience with Keller's conjecture, where the (admittedly large) graphs stumped many clique-finding algorithms. $\endgroup$
    – Peter Shor
    Jun 3, 2018 at 12:42
13
$\begingroup$

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."

Improve this answer
$\endgroup$
1
  • $\begingroup$ Actually, the problem is in $\mathsf{FPL}$ (see this nice presentation on parameterized complexity), i.e. if we fix a nesting-depth of type declarations, then there exists a linear time algorithm. In general, parameterized complexity might be something that OP is interested in. $\endgroup$
    – Watercrystal
    Jun 2, 2018 at 22:58
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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