Sorry, an error occurred while loading the content.

## [Computational Complexity] Why do I find this result interesting- MOD 17 SAT

Expand Messages
• 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
Message 1 of 1 , Oct 17, 2007
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
Your message has been successfully submitted and would be delivered to recipients shortly.