No. Many engineers AND mathematicians worked for a long time to get us to a stage where Amazon can solve a billion SMT problems a day. To contribute, all of them had to understand the theory this article calls overrated.
No. Many engineers AND mathematicians worked for a long time to get us to a stage where Amazon can solve a billion SMT problems a day. To contribute, all of them had to understand the theory this article calls overrated.
2. That the worst-case is very hard usually tells you that many instances will be hard (unless you discover an easy subclass), as is the case here. And when many "natural" instances are easy, that means that the problem is more interesting than perhaps previously thought, and it requires and receives more research, not less. If most instances are near the worst case, it means you know all there is to know about the problem; when they're not, it means there's more to study.
But my favourite example (shown here in Java) demonstrates the difficulty of analysing simple, realistic programs without necessarily being undecidable:
long foo(long x) {
if (x <= 2 || (x & 1) != 0)
return 0;
for (var i = x; i > 0; i--)
if (bar(i) && bar(x - i))
return i;
throw new Error();
}
boolean bar(long x) {
for (var i = x - 1; i >= 2; i--)
for (var s = x; s >= 0; s -= i)
if (s == 0)
return false;
return true;
}
Even in this case where even the input space is finite (and so everything here is definitely decidable), we simply don't yet know whether there is some x for which foo(x) throws, let alone if we made the input unbounded by using BigInteger instead of long.