Gordon Moore formulated his famous law in a paper dated fifty years and five days ago. We all have seen how Moore's law has changed real-world computing, but how does it relate to computational complexity?
In complexity we typically focus on running times but we really care about how large a problem we can solve in current technology. In one of my early posts I showed how this view can change how we judge running time improvements from faster algorithms. Improved technology also allows us to solve bigger problems. This is one justification for asymptotic analysis. For polynomial-time algorithms a doubling of processor speed gives a constant multiplicative factor increase in the size of the problem we can solve. We only get an additive factor for an exponential-time algorithm.
Although Moore's law continues, computers have stopped getting faster ten years ago. Instead we've seen the rise of new technologies: GPUs and other specialized processors, multicore, cloud computing and more on the horizon.
The complexity and algorithmic communities are slow to catch up. With some exceptions, we still focus on single-core single-thread algorithms. Rather we need to find good models for these new technologies and develop algorithms and complexity bounds that map nicely into our current computing reality.
As far as younger readers of Computational Complexity (and related weblogs) are concerned --- readers in need of family-supporting career-sustaining jobs --- the main news of the past month is arguably not the Roco/Li-Yang complexity hierarchy theorem (marvelously ingenious as this theorem is), but rather the $120M/5yr investment by the Swiss-based pharmaceutical corporation Sanofi in the Portland-based quantum simulation corporation Schrödinger.
ReplyDeleteRoughly speaking, that's a large enough investment to support (very approximately) five hundred person-years of complexity-theoretic research.
The enterprise rationale for this investment reflects sustained Moore's Law-type progress not only in computing hardware, but also in storage, networking, sensing, and (most of all) algorithms.
It is instructive to project the levels of job-creating investment that will result if this progress is sustained. Sanofi's $120M quantum-simulation investment is about 0.000875 of Sanofi's market capitalization (presently ~$137B). The aggregate market capitalization of the ten largest pharmaceutical corporations is ~$1.36T (Pfizer, Novartis, Sanofi, Roche, Merck, GlaxoSmithKline, AstraZeneca, Eli Lilly, Abbott, and McKesson), and so a bandwagon of investment by top-rank pharmaceutical corporations would yield a near-term quantum-simulation research investment of ~$1.2B/5yr.
Further increases in algorithmic accuracy and efficiency, sustained through coming decades, would amply justify further increases in research investment — increases potentially of multiple orders of magnitude.
Conclusion Research news this month provides ample "Moore's Law" reason for young researchers in complexity theory and quantum simulation theory to be optimistic about job and career prospects.
Provided that increases in algorithmic efficiency, simulation accuracy, sensing capability, and computational economy, all can be sustained at their historic Moore's Law pace.