Let SAT17 be the set of formulas such that the number of satisfying assignments is a multiple of 17.
If SAT17 ≤m S, S sparse, then SAT17 ∈ 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.
For those of us who are not in the know, can you please say why mod 17, rather than some other prime? Is it suspected this result is true modulo other primes or is 17 really special?
ReplyDelete17 is not special.
ReplyDeleteSee my writeup that I
point to. Works for any
number.
bill g.
I think it's pretty intuitive. What do you mean by interesting?
ReplyDeleteFrom context, interesting == worthy of attention / spending time going over in class, perhaps? As for further reasoning, that's probably the question, yes? :)
ReplyDeleteHow different is the result (or the proof) from Mahaney's theorem?
ReplyDeleteIs it also true that if SAT_p is not in P then it's NP-Complete?
ReplyDeleteI'm actually not entirely sure why I find P!=NP? interesting, since if the answer is "TRUE", it's only a proof for a very intuitive claim, and if the answer is "FALSE", I'm pretty sure the polynom would be so big that the NP-hard problems would still remain infeasible.
ReplyDeleteI think the main reason I find it interesting is just that it sounds so intutively obvious, but still no one has been able to prove it. Okay, also P!=NP is a big assumption that the entire complexity field is built on, so it's interesting to find out if its really true, but still, I'm not sure why it's interesting in the "if someone who doesn't know anything about computer science asked me why it's interesting I could explain" kind of way.
hi,dear all,sorry to post an irrelevant question here.
ReplyDeleteI wonder who can kindly give me some links of the "theory/algo qualifying exams" from univerisitys such as MIT,Princeton,Berkeley,CMU,Stanfordand Harvard(not limited to these schools).
Many thanks!
All universities publish their qualifying examinations (if they have them) in a single online repository; the UQED (University Qualifying Exam Depository). I've embedded a direct link as follows:
ReplyDeleteDirect Link Here
dammit number 9! i completely fell for that.
ReplyDeleteThe direct link from the previous post points to some song on YouTube.
ReplyDeleteThis blog has officially hit rock bottom. Sigh.
Sorry,I can't find that UQED. Thanks anyway.
ReplyDeleteAny other students or professors in these universities can give me a hand on this?
I found that UIUC,Gatech,Wisconsin had put there qualifying exams on their theory group web,but seems others did not:-(
Not every school has qualifying exams.
ReplyDeleteThey have finally posted the official FOCS 2007 trailer:
ReplyDeletehttp://people.csail.mit.edu/konak/focs_2007_trailer.html