BILL: In 2007 the best student paper award at COMPLEXITY went to Ryan Williams for proving that SAT cannot be done in time O(n^{1.801...}) and O(n^{o(1)}) space!! The constant 1.801 is actually 2cos(π/7). (The paper is Time Space Tradeoffs for Counting SAT mod P. Note that the space is n to the little-o(1) which would include log space.)

STUDENT: Doesn't everyone think SAT is not in P?

BILL: YES.

STUDENT: So what's the big deal in proving that SAT is not in time O(n^{1.801...}) and not much space?

BILL: Its a stepping stone towards better lower bounds!

STUDENT: Are better lower bounds using these techniques likely?

BILL: Well, it is thought that these techniques cannot possibly get beyond SAT not in O(n^{2}).

STUDENT: So... why is it such a good result?

BILL: Actually he proved more than that. He proved that, for all but one prime p, finding the number of satisfying assignments mod p requires O(n^{1.801}) space if you insist on O(n^{o(1)}) space.

STUDENT: Is the*number of satisfying assignments mod p problem*a problem people care about?

BILL: Complexity Theorists care about it!

STUDENT: I meant real people!

BILL: Um, ur...

STUDENT: Are there any interesting upper bounds on the*number of satisfying assignments mod p*problem so that the lower bounds are a counterpoint to them?

BILL: YES! There are some poly upper bounds are known for planar read-twice monotone formulas mod 7.! (see this paper by Valiant.)

STUDENT: Do people care about the number of solutions of planar read-twice monotone formulas mod 7?

BILL: Complexity Theorists care about it!

STUDENT: I mean real people! Oh. Are we entering an infinite loop?

BILL: The planar read-twice-monotone-formulas-mod-7 result is an example of a very powerful framework for algorithms.

STUDENT: So that paper may be important, but why is the SAT time-space tradeoff paper important?

I like these results, but STUDENT raises a good question: Are Time Space Tradeoffs for SAT important? IS SAT mod p important? I would argue YES since they are absolute lower bounds and there techniques*combined with something else*may yield more interesting results. However, if you have better arguments please leave comments.

Should Time Space Tradeoffs for SAT be taught in a grad theory course? There is one in Arora-Barak that is not hard. Hence it likely*will*be taught. If you teach it I*hope*you have students challenge you as STUDENT challenged me. It will mean they are awake and care. However, be prepared to answer them.

When this was taught in seminar recently the question arose: In the paper Time space Lower bounds for Satisfiability by Fortnow, Lipton, van Melkebeek, Viglas showed the following: For all c < φ (the golden ratio) there exists d such that SAT cannot be solved in time O(n^{c}) and space O(n^{d}). The techniques are such that it could have been proven in the 1970's. So why wasn't it? The seminar speculates that back then people were not so pessimistic about lower bounds to consider this a problem worth looking at. Now people do.

--

Posted By GASARCH to Computational Complexity at 2/03/2010 10:13:00 AM