[Computational Complexity] Why do I find this result interesting- MOD 17 SAT
- I find the following result to be really interesting but can't quite say why: (For this exposition &lem means poly-m-reduction)
Let SAT17 be the set of formulas such that the number of satisfying assignments is a multiple of 17.
If SAT17 &lem S, S sparse, then SAT17 \in P.This is one of those results where the proof in the literature is hard because they prove something far more powerful (btt reductions- and more). Hence I have my own exposition that I made for my class here.
I presented it in class recently and the students questioned why it was interesting. I can usually answer questions like this (even about such things as the Polynomial VDW theorem) but this one is harder to say. I DO find it interesting (not just the proof, but the result) but can't quite say why.
SO, here is my challenge: either tell me a reason the result is interesting OR tell me a result that YOU find interesting but can't quite say why.
Posted By GASARCH to Computational Complexity at 10/17/2007 02:22:00 PM