[dkarl]

But complexity theory aims at describing the performance of A over the space of all problem instances and it does so by abstracting away from individual problem instances.

I appreciate the effort to extend the story into CS, but I wonder if you have to be familiar with the particular work he's alluding to. The charge (as leveled against theoretical physics) is not that some people do pure mathematical work for the sake of beauty. The charge is that people who are supposed to be applying mathematics to reality are instead prioritizing mathematics and neglecting reality. To extend the analogy to CS, he must be talking about researchers supposedly trying to model real systems but instead just chasing beautiful math, but he isn't specific. Is it obvious to people in the know who or what he's talking about?

For practical programmers, I think the problem is the reverse of being "lost in math." Practical programmers use extremely general theoretical results because they don't want to do math, not because the math is more beautiful. If they applied the information they know about their particular problem, they could get more useful mathematical results, but since they want to stay as far away from (doing) theory as possible, they use whatever facts they remember from class, which are ironically the most purely theoretical ideas because those are the simplest and easiest to remember.

[UncleMeat]

SAT is NP-Complete. In principle, this means that SAT solvers don't scale. If we stopped here then we would never have developed symbolic execution. It turns out that SAT and SMT solvers do scale for lots of real world inputs. Cook's proof is amazingly elegant and powerful but fails to inform real development.

[tikhonj]

SAT solvers only scale sometimes. Complexity theory is a starting point for understanding why this "sometimes" is inevitable, but it never even implies that NP-complete problems are never tractable. Complexity theory gives us an understanding of how powerful and expressive SAT is which very much does inform real development.

Arguing that "SAT is NP-complete and therefore useless" is not misusing complexity theory, it's misunderstanding complexity theory—not misunderstanding some deep result or non-trivial consequence of complexity theory, but misunderstanding the fundamentals that are covered in the first lecture of the first class on the topic.

[bonoboTP]

It's common. My lecturer in the first lecture gave a motivation why we learn about this saying:imagine your boss proposes you compute <whatever>, then you - informed by this lecture - will recognize it belongs to an infeasible complexity class and can tell your boss it won't be possible.

We did learn the definitions but "worst case" was never highlighted as such, it was naturally assumed. The closest we got was the discussion that constant factors may matter for small problems and O analysis masks those differences.

[dllthomas]

> tell your boss it won't be possible

I mean, if your boss is demanding a solution that's both accurate and fast on every input, you can tell your boss that showing P=NP is probably out of scope of your project. But that's the start of a discussion about how to step back from that ideal, not the end of a discussion about the potential product.

[BucketSort]

This has been a common point of complaint in Physics since Einstein, and probably before. The idea that you can come up with ideas about how the universe works in the absence of experimentation doesn't sit right with many scientists. There are many scientists, like Edward Witten, that are working on things that are purely mathematical at the moment, and to some it seems like an inbred mathematical fantasy. In their defense, this is why what they do is called theoretical physics.

[chopin]

>In their defense, this is why what they do is called theoretical physics.

In my opinion, theoretical physics is about explaining observable phenomena in a falsifiable way (I am with Popper here). Otherwise an omnipotent god would be an equally good explanation for a given phenomenon.

[BucketSort]

I consider their role to be the people that are exploring mathematical models of phenomena that may or may not exist, so when the regular physicists find something new, there's some mathematical precedent they can use. Physics is about explaining "observable phenomena in a falsifiable way," theoretical physics is broader than that. I think they both have their place. I don't know why people put them at odds against each other, I thought they have been shown to have a long and fruitful relationship ( the experimentalists and the mathematicians ). The relationship between Faraday and Maxwell should be the shining example that shows how the two sides of understanding nature balance each other.

[through_17]

"the particular work" he is referencing is computational complexity theory; a long-running attempt to mathematically characterize which problems can be efficiently solved with computers and which cannot. I work in complexity theory, and this does make the objects of his criticism obvious to me. I'll try to explain below.

Think of "problems" as abstract primitives: sorting, search, graph operations, optimization, etc. To give a concrete example, let's take a particular search problem: boolean satisfiability (SAT). The input is boolean formulas, and the output is "an assignment to the variables of this formula that make it TRUE."

Some problems are "NP-complete". The definition of NP isn't important for our discussion here. What is important is that NP-completeness or lack thereof is indeed a "beautiful" way to classify problems. Further, we expect NP-complete problems to be impossible to solve efficiently on every input. This is what the article means by "worst-case" or "overly pessimistic" theories.

SAT is NP-complete, so "classical complexity" would predict that SAT cannot be efficiently solved with computers. But often, SAT can be solved efficiently "in practice" using simple heuristics. So Moshe would say that classical complexity is simply wrong; it doesn't describe the "real-world" behavior of actually trying to solve SAT. While difficult-to-process formulas may exist, we "just happen" to only encounter easy-to-process formulas.

So, to summarize: the article criticizes researchers who focus only on worst-case complexity. While the theory is beautiful, we can point to many problems for which it does not accurately predict performance.

I think this criticism is a little strange, because most complexity theorists also work on "average-case" complexity; the study of when "typical" inputs are difficult vs easy to solve. This is mentioned at the very end of the article. Any working complexity theorist would immediately list these problems with worst-case complexity, and explain that it is an imperfect and primitive theory compared to how we would really want to understand when and how these problems are difficult. There is a great deal of work trying to understand what about each formula makes it difficult or easy to process, and why.

The issue is, we are nowhere near understanding even worst-case complexity. So theoretical research often toggles back and forth between the two settings, trying to make progress overall.

Computational complexity theory is a fundamental mathematical field that will only occasionally produce enough understanding to impact practice. For an example, see:

https://www.youtube.com/watch?v=FGtsqEwANWY&feature=youtu.be...

[dkarl]

So, to summarize: the article criticizes researchers who focus only on worst-case complexity. While the theory is beautiful, we can point to many problems for which it does not accurately predict performance.

I still don't get it, because it's okay for some people to be working on purely theoretical problems, motivated by mathematical curiosity and aesthetics. Is there a lack of people working on more concrete problems, bridging the gap between theory and practice? Are there outstanding problems arising from practice that are ignored because supposed "applied" researchers don't actually care about applications?

I think this criticism is a little strange, because most complexity theorists also work on "average-case" complexity

That sounds almost as theoretical as worst case to me. I would expect "applied" complexity theory to provide a theoretical framework for how a practitioner can add information that they know about how their problem differs from the aesthetically ideal problems that arise in theory. Like, my factory floor is not a frictionless plane, aha, here's how you measure a "coefficient of friction," and here's a new equation where you can see how the coefficient of friction affects the results. Or, my dataset isn't a uniformly random blob of bits, so is there a statistical property I can measure that lets me estimate the probability of the working memory of my algorithm exceeding 2.4 times the size of the input size?

[through_17]

Let me clarify: average-case does not just mean "over the uniform distribution", though that is of course one distribution of inputs we can study (mostly with applications to cryptography). Average-case complexity can be studied over any family of distributions.

Finding ways to characterize hardness and easiness in terms of underlying structure to those input distributions is exactly what average-case complexity tries to accomplish. The "holy grail" is to classify problems over efficient distribution of inputs. That is, first make the fairly reasonable assumption that the family of formulas you actually run (say) SAT-solvers on came from an efficient computation ("nature", or people coming up with problems). Then, identify properties of those distributions that you can measure and "blame" intractability on.

For example, there's a huge amount of work on these types of parameters for SAT instances. See: https://people.csail.mit.edu/rrw/backdoors.pdf

This type of work could, eventually, directly inform practice.

And of course I think it is okay for some researchers to work on purely theoretical or worst-case problems. Insights from worst-case complexity are often useful in solving the more difficult problems of average-case complexity; it is useful to know where and how the theories diverge.

Reconsidering, I guess I just don't understand the article at all. Maybe he's arguing that TCS doesn't have this problem because we have a hierarchy of theories, where worst-case complexity inspires average-case complexity inspires parameterized average-case complexity which could someday be used in the real world. Over very long timescales (think, centuries) I think complexity theory will produce practical insights.

[dkarl]

This type of work could, eventually, directly inform practice.

Are there any problems taken directly from practice that complexity researchers are working on and using as context to define shortcomings in existing theory? Maybe that's what he's talking about, expanding on theory that "could, eventually, directly inform practice" and calling that "applied research" instead of tackling practical problems directly.

[through_17]

Yeah, a lot of the work on average-case SAT is directly informed by what industrial benchmarks look like.

Further from "core complexity," a lot of the work on machine learning primitives is also directly informed by instances from practice. See the "manifold hypothesis" :

https://deepai.org/machine-learning-glossary-and-terms/manif...

[bitL]

It's like you have some problems in graph theory that are NP-Complete/Hard, so in theory you are out of luck. But if you restrict yourself to a certain type of graphs, or you change your problem from e.g. computing a chromatic number on a certain type of graphs to instead decide if for a given K such K-coloring exists, suddenly there is a polynomial algorithm. And practically-wise, you might be fine with just K={2,3,4,5} and couldn't care less about other values of K for your practical case; so while in general you can't solve it, in practice you have a fast algorithm you run 4x in a row and are done.