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.
(more…)
15 August 2010
13 August 2010
P not equal to NP (P ≠ NP) consequences
9 August 2010
Deolalikar’s manuscript
Given the sudden influx of visitors, it seemed apposite to talk about Vinay Deolalikar’s manuscript titled 
15 April 2010
k-ISOLATED SAT
How fast can one decide if a SAT instance has an isolated solution? (more…)
10 February 2010
Is P=NP a reasonable hypothesis?
Does it even make sense to ask “what if P = NP?”, or is this nonsense? (more…)
Constraints 
A simple reduction
Tags: computational complexity, k-ISOLATED SAT
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…)