How fast can one decide if a SAT instance has an isolated solution? (more…)

## 13 August 2010

## 15 April 2010

## 23 March 2010

### Immediate SAT restarts?

SAT solvers have been moving to more frequent restarts. Can restarts completely replace local search? (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…)

### P=NP consequences

The consequences of P = NP would be “potentially stunning”, according to Stephen Cook, in his Millennium Prize overview of the P versus NP problem.

Is this really true? (more…)

## P not equal to NP (P ≠ NP) consequences

Tags: computational complexity

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…)