Lane A. Hemaspaandra
Abstract
This Issue Warmest thanks to David and Josh for starting all of our summers with their fascinating column, \Beyond number of bit erasures: New complexity questions raised by recently discovered thermodynamic costs of computation." Future Issues Please stay tuned for the coming issues' articles in the Complexity Theory Column, namely, Lane A. Hemaspaandra and Holger Spakowski (tentative topic: team diagonalization), William Gasarch (not-at-all-tentative topic: the third P versus NP poll), (again!) William Gasarch (tentative topic: the muffin problem), and Emanuele Viola (topic: TBD).
Recommendations
SIGACT news complexity theory column 36
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,...
SIGACT News Complexity Theory Column 100
This is column number 100, and Bill Gasarch has very kindly made it an event! In particular, this issue's column is the third of Bill Gasarch's series of polls on the eld's thoughts on P vs. NP (and other central issues in complexity). The rst two polls ...
SIGACT news complexity theory column 35
I was surprised and delighted at a recent conference when the complexity class Θ2p suddenly popped up in a talk (by Markus Holzer on work by him and Pierre McKenzie) where it is was not exactly something one would have before-hand expected to come into ...
Comments