4 ms·
No. NP-Completeness was first defined in the 70s. That’s literally a foundation of much subsequent work. The depth of techniques used back then was mostly just
by Ar-Curunir 5y ago
No. NP-Completeness was first defined in the 70s. That’s literally a foundation of much subsequent work. The depth of techniques used back then was mostly just elementary combinatorics, probability, and number theory. In comparison, much work nowadays require complex algebra, advanced combinatorics, and deeper mathematics like measure theory.
(This is not to downplay the work of the pioneers who discovered these foundational concepts; just to point out that they used less sophisticated mathematical tools)
- AnimalMuppet 5y agoWhat in computer science requires measure theory?
- Ar-Curunir 5y agoEg: https://simons.berkeley.edu/talks/michael-mislove-2016-08-30 https://simons.berkeley.edu/talks/michael-mislove-2016-08-30
- AnimalMuppet 5y agoNo, I'm not going to watch an hour-long video for the answer. The intro seems to be saying that "domains" (undefined) are related to CS, and also related to measure theory. That's... not much to go on...
- bidirectional 5y agoThere's an abstract right there: > Measure theory has played an important role for domains in modeling probabilistic computation.
- AnimalMuppet 5y agoYup. Read it. Without a definition or context for "domains", it doesn't tell me much.
- bidirectional 5y agoWell I'm not sure what to say. Domains require measure theory if you want to model probabilistic programming languages. Domain theory is part of CS. If you don't know what a domain is, that's kind of on you to read up on.