<p>The <a href="https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system" rel="noreferrer">Hindley-Milner</a> 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!</p>

<p>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 <em>"Experience without theory is blind, but theory without experience is mere intellectual play."</em></p>

CC BY-SA 4.0
2018-06-02T22:58:19.337Z
Actually, the problem is in $\mathsf{FPL}$ (see this nice [presentation on parameterized complexity](https://tcs.rwth-aachen.de/~sanchez/slides/Raleigh2014.pdf)), 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.
Watercrystal
CC BY-SA 4.0
2018-05-22T07:02:09.670Z
2018-05-22T07:02:09.670Z
Andrej Bauer
<p>More examples, mostly from programming languages:</p>

<ol>
<li>k-CFA (k-Control Flow Analysis) is EXPTIME-complete (Van Horn &amp; Mairson 2008), but whole-program optimizing compilers like MLton perform it anyway. The compile times are long, but rarely disastrous.</li>
<li>Resolving (dynamic) overloading is generally NP-complete (Palsberg 2012). But then it is rarely a problem in the real world.</li>
<li>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.</li>
<li>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.</li>
<li>The decision problem for Presburger arithmetic is really complex (Fischer &amp; Rabin 1974), but Bill Pugh's decision algorithm, the Omega test (Pugh 1991), runs generally within low-order polynomial-time.</li>
</ol>

<p>Remember that big-$O$ (and thus complexity classes) is about <em>asymptotic</em> 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. </p>

<hr>

<p>References:</p>

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

<p>[2] <a href="http://web.cs.ucla.edu/~palsberg/paper/dedicated-to-kozen12.pdf" rel="noreferrer">http://web.cs.ucla.edu/~palsberg/paper/dedicated-to-kozen12.pdf</a></p>

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

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

CC BY-SA 4.0
2018-05-23T07:57:16.963Z
2018-05-23T08:05:48.060Z
2018-05-23T08:05:48.060Z
xrq
<p>training neural networks using gradient descent methods is also proven to be badly np-hard problem <a href="https://www.cs.utexas.edu/~klivans/crypto-hs.pdf" rel="nofollow noreferrer">https://www.cs.utexas.edu/~klivans/crypto-hs.pdf</a>
but are generally solvable in practice.</p>

CC BY-SA 4.0
2018-05-29T11:10:12.060Z
2018-05-29T11:10:12.060Z
thecomplexitytheorist
<ul>
<li><p>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 <a href="https://cstheory.stackexchange.com/q/37886/129">this related question</a> and its answers.</p></li>
<li><p>Clique finders are also shockingly good "in practice"</p>

<ul>
<li><p>With respect to clique finders, (part of the) explanation is given
by an average case analisys of the algorithms in question.</p>

<p>See <a href="https://www.sciencedirect.com/science/article/pii/S0166218X18300167?via%3Dihub" rel="nofollow noreferrer">https://www.sciencedirect.com/science/article/pii/S0166218X18300167?via%3Dihub</a></p></li>
</ul></li>
<li><p>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</p></li>
<li><p>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.)</p></li>
<li><p>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!</p></li>
<li><p>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.</p></li>
</ul>

CC BY-SA 4.0
2018-05-25T06:14:37.280Z
Thanks Joshua, I am giving it to you for the most interesting / broad problems suggested.
Konstantinos Koiliaris
CC BY-SA 4.0
2018-05-28T17:16:00.657Z
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 
CC BY-SA 4.0
2018-06-02T23:11:55.287Z
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](https://arxiv.org/abs/1705.03283) recently showed exponential lower bounds for this method and constructed (practically) hard instances.
Watercrystal
CC BY-SA 4.0
2018-06-03T05:33:03.260Z
@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
CC BY-SA 4.0
2018-06-03T05:36:35.787Z
@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
CC BY-SA 4.0
2018-06-03T11:45:02.993Z
@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
CC BY-SA 4.0
2018-06-03T12:42:12.653Z
I just have experience with [Keller's conjecture](https://en.wikipedia.org/wiki/Keller%27s_conjecture), where the (admittedly large) graphs stumped many clique-finding algorithms.
Peter Shor 
CC BY-SA 4.0
2018-05-22T04:24:47.527Z
2018-05-28T07:38:27.117Z
2018-05-28T07:38:27.117Z
Joshua Grochow
<p>Recently, I went through the <s>painful</s> 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 <em>(PTIME, intractability, uncomputability)</em>, while others seem to come more natural <em>(problem classification via reductions, time and space as resources, asymptotic analysis)</em>. Everything was going great until I accidentally admitted that <strong>SAT</strong> 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 <s>crap</s> math that he should not care for. Well...</p>

<p>¯\_(ツ)_/¯</p>

<p>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, </p>

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

<p>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? </p>

<p><strong>TL;DR:</strong> What are <strong>problems that are counter-intuitively solvable in practice?</strong> 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?</p>

<p><strong>EDIT #1:</strong> In trying to answer my last discussion question about such a <strong>characterization</strong>, I was introduced to <em>smoothed analysis</em> 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.</p>

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

CC BY-SA 4.0
2018-05-21T03:24:20.360Z
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
CC BY-SA 4.0
2018-05-21T04:11:22.560Z
Graph isomorphism is a natural candidate.
D.W.
CC BY-SA 4.0
2018-05-21T17:00:16.597Z
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
CC BY-SA 4.0
2018-05-22T07:49:20.517Z
@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
CC BY-SA 4.0
2018-05-22T20:04:12.357Z
@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
CC BY-SA 4.0
2018-05-23T05:05:58.167Z
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
CC BY-SA 4.0
2018-05-23T07:53:30.443Z
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
<cc.complexity-theory><ds.algorithms><np-hardness>
Problems that are counter-intuitively solvable in practice?
Konstantinos Koiliaris
# Problems that are counter-intuitively solvable in practice?

(Asked by: username_0 on 2018-05-21)

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.

**Tags:** cc.complexity-theory, ds.algorithms, np-hardness
> **Comments:**
> **username_1**: 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.  
> **username_2**: Graph isomorphism is a natural candidate.  
> **username_0**: 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".  
> **username_3**: @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).  
> **username_0**: @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.  
> **username_4**: Most program analysis questions are undecidable [Rice], but many program analyzers are pretty fast. That's, of course, because humans write simple programs, mostly.  
> **username_5**: 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.  

---

## 4 answers

### Answer by username_10 on 2018-05-22. Score: 16 | Accepted answer

* 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](https://cstheory.stackexchange.com/q/37886/129) and its answers.
* Clique finders are also shockingly good "in practice"

  + With respect to clique finders, (part of the) explanation is given
    by an average case analisys of the algorithms in question.

    See <https://www.sciencedirect.com/science/article/pii/S0166218X18300167?via%3Dihub>
* 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.

> **Comments:**
> **username_0**: Thanks Joshua, I am giving it to you for the most interesting / broad problems suggested.  
> **username_11**: 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.  
> **username_7**: 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](https://arxiv.org/abs/1705.03283) recently showed exponential lower bounds for this method and constructed (practically) hard instances.  
> **username_10**: @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.  
> **username_10**: @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.)  
> **username_7**: @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.  
> **username_11**: I just have experience with [Keller's conjecture](https://en.wikipedia.org/wiki/Keller%27s_conjecture), where the (admittedly large) graphs stumped many clique-finding algorithms.  

---

### Answer by username_6 on 2018-05-22. Score: 13

The [Hindley-Milner](https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system) 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."*

> **Comments:**
> **username_7**: Actually, the problem is in $\mathsf{FPL}$ (see this nice [presentation on parameterized complexity](https://tcs.rwth-aachen.de/~sanchez/slides/Raleigh2014.pdf)), 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.  

---

### Answer by username_8 on 2018-05-23. Score: 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.


---

### Answer by username_9 on 2018-05-29. Score: 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.


---

