{"id":1185,"date":"2012-12-02T18:58:16","date_gmt":"2012-12-02T17:58:16","guid":{"rendered":"http:\/\/cerezo.name\/blog\/?p=1185"},"modified":"2024-10-14T13:47:06","modified_gmt":"2024-10-14T11:47:06","slug":"commemorating-computational-complexity","status":"publish","type":"post","link":"http:\/\/cerezo.name\/blog\/2012\/12\/02\/commemorating-computational-complexity\/","title":{"rendered":"Commemorating Computational Complexity"},"content":{"rendered":"

Fifty years ago, two researchers started writing this seminal paper<\/a>, kicking off the research field of computational complexity, the core of computer science, with now tens of thousands of publications.<\/p>\n

Although the concepts and ideas underlying the paper were not new, as a letter by Kurt G\u00f6del<\/a> show us, it was the foundational moment for a field that still produces deep, beautiful and practical results: in the last decade, Williams\u2019 lower bound on non-uniform circuits<\/a>; Agrawal-Kayal-Saxena primality test<\/a> that included primality testing in P (although Miller-Rabin<\/a> and Solovay-Strassen<\/a>   primality tests still live strong since they are much faster than AKS<\/span>) or Vassilevska\u2019s lower bound on matrix multiplication<\/a>.<\/p>\n

I see tons of start-ups and projects fail because they ignore the most basic algorithmic prudence: that is, that only sub-logarithmic algorithms should be accessible to the mass-public is one the ignored maxims of the computer industry that can only be learned by the proper interpretation of the absence of market offerings refuting it (vg. regular expressions within search engines\u2019 queries, which could run in exponential time; or all the AI<\/span> promises about solving optimization problems that never delivered).<\/p>\n

Speaking with some researchers lately, they expressed the hope that the coming end of Moore\u2019s law would vindicate this field, making its results much more relevant: and although they were absolutely right in that proportionally more resources will be directed towards these ends, they also failed to consider that the likely crash following this event may also reduce the total, aggregated opportunities.<\/p>\n","protected":false},"excerpt":{"rendered":"

Fifty years ago, two researchers started writing this seminal paper, kicking off the research field of computational complexity, the core of computer science, with now tens of thousands of publications. Although the concepts and ideas underlying the paper were not new, as a letter by Kurt G\u00f6del show us, it was the foundational moment for [\u2026]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"wp_typography_post_enhancements_disabled":false,"ngg_post_thumbnail":0},"categories":[9,13],"tags":[],"_links":{"self":[{"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/posts\/1185"}],"collection":[{"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/comments?post=1185"}],"version-history":[{"count":15,"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/posts\/1185\/revisions"}],"predecessor-version":[{"id":1569,"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/posts\/1185\/revisions\/1569"}],"wp:attachment":[{"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/media?parent=1185"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/categories?post=1185"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/tags?post=1185"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}