5 ms·

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

by dkarl 8y ago

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.

BucketSort 8y ago
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 8y ago
  >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 8y ago
    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 8y ago
"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&list=PLgKuh-lKre12S9FgcsgxlaoEkgNZuqeNc https://www.youtube.com/watch?v=FGtsqEwANWY&feature=youtu.be...
- 8y ago
UncleMeat 8y ago
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 8y ago
  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 8y ago
    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 8y ago
      > 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.

by dkarl 8y ago

BucketSort 8y ago

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 8y ago
>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 8y ago
  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 8y ago

"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&list=PLgKuh-lKre12S9FgcsgxlaoEkgNZuqeNc https://www.youtube.com/watch?v=FGtsqEwANWY&feature=youtu.be...

8y ago

UncleMeat 8y ago

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 8y ago
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 8y ago
  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 8y ago
    > 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.