[chrisandchips]

> This is true in principle, but the reality is more complicated. When we say “NP-complete is hard” we’re talking about worst-case complexity, and the average-case complexity is often much more tractable. Many industry problems are “well-behaved” and modern SAT solvers can solve them quickly.

This is a really cool point, no one ever mentioned this to me when I learned about this stuff at university. I wonder though, is there data for this ? Are businesses willing to take the risk and how do they mitigate ?

I'm not sure how popular they are in the wild, but there are a lot of approximation algorithms as well for solving version of these problems that are almost-but-not-quite the same. I wonder if that's just what lots of real-world use cases actually need.

[yarg]

I think the complexity of the problem is such that even a lot of lecturers don't really understand it.

I remember in one lecture where the dude drew an unweighted graph on the board, claiming it to be in NP.

But he'd already proven it to be planar (by construction), which (and correct me if I'm wrong) simplifies the problem to P.

[JohnKemeny]

SAT is NP-complete even when the variable-clause graph is planar.

Vertex cover is NP-complete on planar graphs even if each vertex has at most three neighbors.

Travelling Salesman is NP-complete on planar graphs.

So is independent set, dominating set, 3-coloring...

[yarg]

It's not the travelling salesman - as per the description it's an unweighted graph.

This reduces the problem from finding the shortest hamiltonian cycle to finding any such cycle.

[Vervious]

it's actually a very open question, even theoretically, whether we can build an "hard on average problem" from a "worst case hard problem" in NP. This is why we haven't yet managed to design cryptography from 3SAT, for instance.

[chrisandchips]

That's super interesting! I'd love get the names of some people working on that stuff.