Hacker News Reader

Comment by ragall | Hacker News Reader

> Saying it's overrated is like saying calculus is overrated because most people don't need to use it every day.

You should stop thinking by analogy.

The article was showing the difference between mathematicians and engineers. For the mathematicians that created Computation Science, the only interesting solutions are complete solutions to general questions, whereas for engineers it's perfectly acceptable to eliminate some corner cases, thereby solving a reduced and simplified version of the general problem.

View on HN

> For the mathematicians that created Computation Science, the only interesting solutions are complete solutions to general questions

Except that's not really true, which is the whole point of the finer computational classes. If many instances are far from the worst case, that tells you something interesting about the class, which is why we have things like parameterised complexity. People who think that the theory is only interested in the general case of the broad classes you learn as an undergrad are just not sufficiently familiar with the theory.

> For the mathematicians that created Computation Science, the only interesting solutions are complete solutions to general questions

There is a bunch of research devoted to Polynomial Time Approximation Schemes (PTAS). Mathematicians also take part in it.

I did study a bit of complexity theory back in the day, and it does seem a bit theoretical, but not so long ago, I ran into an very prominent manifestation. To help someone, I had created a simple web page which also had an input field for the css that was applied directly to the page. To avoid flickering and weird effects because of malformed css, I wrote a regexp to check the CSS code. It's a very simple language, after all, and it didn't have to be perfect. It worked well, until at one point, a simple typo locked up Chrome for 1 minute 10 seconds. Parse time just jumped from less than 100ms to 70000ms by adding a single character. That's when you feel what exponential means.

I just want to point out that complexity theory isn't really about analysing the complexity of a particular algorithm (that's the subject of algorithm and data structure analysis, where students learn big-O notation), but about understanding the complexity of a problem independently of any algorithm (i.e. what problems couldn't be tractably solved by any algorithm).

> The article was showing the difference between mathematicians and engineers.

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.

Some mathematicians certainly did, but there's a very large undercurrent in CS, as well as Mathematics more in general, of utter disinterest for applications as well as the idea that the more general a solution, the more "worthy" it is. That was really obvious from the words of the professor cited in the article.

Would you disagree that, given the choice, a solution to every problem is strictly better than a solution so only some problems?

No. Because for let’s say the halting problem the general case says it’s unsolvable, but each specific case is solvable.

1. Not all specific cases are solvable.

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.

Can you give a specific finite program which is undecidable?

A program that enumerates all theorems in ZFC and stops when it proves a contradiction (e.g. true = false). Encoding a program that is equivalent to that directly as a Turing Machine in merely 748 states: https://www.scottaaronson.com/papers/bb.pdf (meaning that we cannot prove an upper bound on the 748th Busy-Beaver number, but there are probably even smaller undecidable TMs).

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.

Yes I disagree, because the algorithm to solve every problem takes longer to run than the remaining age of the universe.

I would to say I support that view. What is the purpose of modern science if not to discover truths you can apply universally? If you state: ‘this particular apple falls to the ground’ thats not a scientific discovery, there must be some general applicability.

There is an entire field of static analysis that is dedicated to practically solving undecidable problems.

You have clearly not encountered theoretical computer scientists. They love to create all kinds of complexity classes and theorems to capture things like heuristics and approximation algorithms and other things which work in practice but not theory.

In fact that’s a big research thrust right now, to understand why many real-world SAT instances are solvable quickly while others are not, and where the threshold between them lies

I studied mathematics, and can attest that the attitude of the professor mentioned in the article is very representative of an older generation of mathematicians. Maybe the younger ones are different.

I also studied mathematics, and I can tell you that this was not my experience.

Rather, if a problem is NP-complete/NP-hard it means that we cannot expect a general fast algorithms for exactly this problem (in other words: more mathematics is required, which mathematicians of course love).

But it is absolutely known that there exist other strategies:

- Develop algorithms that work well in practice and make understanding why they work so well in practice your career.

- Find out whether there exists something that makes the instances that occur in practice different from those instances that were used in the proof that the problem is NP-complete/-hard.

- For optimization problems: develop some fast algorithm which guarantees some approximation factor.

It't not a matter of generations. There are plenty of old mathematicians who are very interested in applications and plenty of young mathematicians who are only interested in generalized abstract nonsense. It's more of a difference in personality that will always be there.

Reply on news.ycombinator.com