SIGACT news complexity theory column 36

Abstract

This current issue's guest column is by Bill Gasarch, and reports on a poll he has conducted on the most famous open question in complexity theory: P=?NP. If Mitsunori Ogihara's prediction that P-vs-NP will not be resolved until the year 3000 is correct, my guess is more than a few students of the history of computer theory will be visiting, long after all the contributors are gone, Bill's column, which will provide a time capsule into the thoughts of many in the field. Who knows? Perhaps there will even be Ph.D. theses devoted to figuring out who these people all are, and just who the (as the students will know from their history of science books) then-Turing/Fields/Nobellaureate Bill Gasarch was making an exception of when he wrote below, "Almost all respondents are people whose opinions can be taken seriously," and great debates may rage over whether he actually meant, by "almost all," "all but a (large) constant number." In light of the fascinating opinions, though, I suspect that but little evidence will be found for that view---even by Ken Regan's Vegans. Surely some M.S. thesis will be written claiming that it was this column---and in particular the superfluous disjunct in Donald Knuth's claim that x ≤ 2048 V x ≤ 4096---that led, in the year 2¹⁰ + 2¹¹, to Donald Knuth's Turing Award being posthumously rescinded and given to Bill Gasarch. However, the Knuth Cult will discover that Donald Knuth's words here are a numerical key that unlocks the secret of the Art of Computer Programming, which, it turns out, when decoded has nothing to do with computers but rather is a skillful telling of the life story of a Danish saint.Warmest thanks to Bill and the dozens of contributors for their time, analyses, and prognostications.Plugs for past and future issues: In 1996 and 1997, SIGACT News Complexity Theory Columns 14 and 15 collected various expert's opinions on the future of computational complexity. If you have not read those opinions already, they are worth a look. And coming in the next few issues we'll have Marcus Schaeffer and Chris Umans on completeness for higher polynomial hierarchy levels, Arfst Nickelsen and Till Tantau on partial information classes, and Ramamohan Paturi on the complexity of k-SAT.

Index Terms

• Theory of computation

  • Computational complexity and cryptography