Loading ...
Sorry, an error occurred while loading the content.

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

Expand Messages
  • GASARCH
    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
    • 0 Attachment
      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.