deterministic 3SAT in O*(1.334^n) time

Robin Moser and Dominik Scheder have put an end to the stream of slight improvements in derandomizing Schöning’s randomized k-SAT algorithm from 1999.

InfiniteStack / TheoryOverflow / CSTheory public beta

The initial batch of questions and answers at the Theoretical Computer Science Q&A forum seems promising. I encourage theoretical computer scientists to take a look, and to consider contributing.

A simple reduction

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.

P not equal to NP (P ≠ NP) consequences

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.

Deolalikar’s manuscript

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”).

TheoryOverflow nearing beta

The TheoryOverflow site was proposed a few weeks ago for discussion of research-level questions in theoretical computer science. I am committed to using this service, and encourage others in the community to try it out.