4 ms·
Serious question: In what ways is CS theory high-impact? I'm particularly interested in any arguments that complexity theory is high-impact (beyond the very us
by lightcatcher 11y ago
Serious question: In what ways is CS theory high-impact?
I'm particularly interested in any arguments that complexity theory is high-impact (beyond the very useful insight that there are some problems for which no polynomial time algorithm is known). I have a pretty good idea of the impact of cryptography and randomized linear algebra (sometimes considered CS theory), but am also interested in hearing about other fields considered CS theory with useful applications.
- jonsterling 11y agotype theory has broad applicability, since it serves as the basis for all modern programming languages design and research. another nice example is kripke logical relations, which can be used to give a model for a programming language in which you can prove certain safety lemmas for critical code.
- gone35 11y agoAgain I'm being a bit self-serving, but I think Neil deGrasse Tyson put it better [1, from 1:35-2:30]: [1] https://www.youtube.com/watch?v=a0SUpwIAjQs&t=1m35s https://www.youtube.com/watch?v=a0SUpwIAjQs&t=1m35s
- swordswinger12 11y agoGraph theory is a good example of this - the asymptotically fastest minimum spanning tree algorithm was made possible by Hopcroft and Karp just drawing weird data structures on a chalkboard until union-find popped out, which gives you near-linear time MST.