Recent online discussion about computational complexity included the notion that the structure of solutions of SAT might be useful in proving separation results. I want to point out a further obstacle to this idea. (more…)
15 August 2010
13 August 2010
During the discussion about Vinay Deolalikar’s manuscript, many people commented about the consequences that would follow if we knew that P ≠ NP. I’d like to discuss these consequences in a little more detail.
9 August 2010
Given the sudden influx of visitors, it seemed apposite to talk about Vinay Deolalikar’s manuscript titled (or in words, “P is not equal to NP”). (more…)
15 April 2010
How fast can one decide if a SAT instance has an isolated solution? (more…)