9
$\begingroup$

I am a high school sophomore who is interested in computer science. I developed a cool algorithm for #SAT, and I'm implementing and doing a science fair project on it. My adviser, who is the best science teacher at my school and is also the AP Comp Sci teacher, told me that she has absolutely no idea what my project is about, and that I need to be able to briefly explain her why #SAT is important in under 5 minutes. I told her SAT reduces to #SAT and tried to explain why SAT is important: I gave her some examples of NP problems, explained her how problems in NP reduce to SAT, and explained how with binary search you can reduce certain optimization problems to SAT, which allows you to fold proteins and make powerful AI models. Unfortunately, she didn't understand me at all. Could you give me a few pointers?

P.S. My adviser asked me what useful problems reduce to #SAT that don't reduce to SAT (assuming some problems in #P are harder than their corresponding NP versions). All I could come up with was finding how many models for a given data set are better than a given model (assuming each parameter of the model is smaller than a given number of bits). I looked for other ones on the web but I couldn't find anything I could understand. Are there any other good applications?

$\endgroup$
  • 2
    $\begingroup$ The permanent (even for matrices whose entries are constrained to be 0 or 1) is #P-complete, so any applications of the permanent are also applications of your algorithm, as long as these applications require you to compute (or approximate) the permanent of some matrix "in practice" (rather than on paper). $\endgroup$ – Yuval Filmus Feb 3 '15 at 3:47
  • $\begingroup$ youve chosen an excellent theoretical project but unf rather advanced/ abstract for high school. an obvious question, how did you learn about the importance of #SAT yourself? there may be some tieins to eg the AP CS curriculum via NP completeness etc, have you taken that class yet? what textbook does it use? if it is a good one, there will be some connections to mine there. suggest dropping by Computer Science Chat for further advice, several grad/ phd students hang out there. & also invite you to cstheory salon to discuss it further. $\endgroup$ – vzn Feb 3 '15 at 5:43
  • $\begingroup$ If I had to explain it to a non-CS/non-math audience, I would: (1) explain what a problem is (you expect a certain kind of input and you want to produce an output based on that input), (2) explain what it means for a problem to be hard, (3) explain the SAT and #SAT problems, (4) state that these problems are hard, and (5) state that finding faster algorithms for problems in general is valued high enough that there is a million dollar prize if you can solve SAT quickly. I hope that helps a little, even though it doesn't totally answer your questions. Have a nice day! $\endgroup$ – Michael Wehar Feb 6 '15 at 16:11
  • $\begingroup$ There are a few problems listed on wikipedia (although you probably already saw this). Here's the link: en.wikipedia.org/wiki/Sharp-P $\endgroup$ – Michael Wehar Feb 6 '15 at 16:31
  • 1
    $\begingroup$ @MichaelWehar Though if you could solve SAT quickly that million dollars wouldn't be worth much to you! $\endgroup$ – Elliot Gorokhovsky Feb 7 '15 at 0:51
6
$\begingroup$

The permanent is #P-complete, even when restricted to $\{0,1\}$-valued matrices. The permanent can be used to compute certain parameters in statistical mechanics, see for example this paper on the dimer covering problem. Since I'm not a physicist, I cannot comment on whether these theoretical statistical mechanics problems are really useful; I suspect that they are not directly useful, but the area itself could lead to useful insights. It could also be the case that some of these parameters are useful on their own, but you'll have to consult with an expert.

Your 5 minute pitch could go something like this:

Statistical mechanics is a beautiful and deep part of physics and chemistry which studies how the emergent behavior of large systems results from microscopic physical laws operating on individual elements. It explains phenomena such as the laws of gasses, magnetization, and transitions between different phases of matter. Statistical mechanics is intimately connected to probability theory, computer science, operations research, and data science.

Many important quantities in statistical mechanics can be formulated as instances of #SAT. An algorithm for solving #SAT exactly or approximately can thus be used to predict physical and chemical phenomena.

This might somewhat overstate the case, but that's how sales pitches go.

$\endgroup$
1
$\begingroup$

This question seems to mix up SAT and #SAT a bit in its wording. Yes, the two are tightly coupled. #SAT is simply defined as the complexity class associated with counting the number of solutions to a SAT problem and widely conjectured to be much harder, but maybe surprisingly, it hasn't been proven. #SAT is not even studied very much in college level complexity theory, it's more of an advanced theoretical research topic.

One way to motivate the importance of #SAT is via Toda's theorem which won a 1998 Gödel prize for it's deep significance. From Wikipedia:

Thus Toda's theorem implies that for any problem in the polynomial hierarchy there is a deterministic polynomial-time Turing reduction to a counting problem.[1]

Also, since SAT and #SAT are not even proven to have different complexity, a reasonable case can be made that understanding #SAT complexity might lead to some insight on the P vs NP problem, which has loads of information and motivation.

$\endgroup$
  • $\begingroup$ re P vs NP see also recent book by Fortnow Golden ticket, P/NP and the search for the impossible $\endgroup$ – vzn Feb 3 '15 at 19:38
  • $\begingroup$ Any application of SAT is an application of #SAT, I'm looking for applications of both. $\endgroup$ – Elliot Gorokhovsky Feb 3 '15 at 19:54
  • $\begingroup$ lol then your question is much different. NP complete problems have extremely broad applications & this is widely documented. see Fortnows book or eg Garey/ Johnson theory of NP completeness. and btw if the AP CS teacher doesnt know what NP completeness is, then s/he should be fired. $\endgroup$ – vzn Feb 3 '15 at 19:58
  • $\begingroup$ Well, the kids who take the class don't even understand simple concepts like binary search so if she knew about it it would be wasted on the students' ears anyway. $\endgroup$ – Elliot Gorokhovsky Feb 3 '15 at 20:13
  • $\begingroup$ Also, can you explain why its difficult to prove Toda's theorem? Because since every problem in NP reduces to SAT which trivially reduces to #SAT. What problems are in PH that aren't in NP? Sorry, I've taught myself everything from Wikipedia so I have a ton of holes in my knowledge. $\endgroup$ – Elliot Gorokhovsky Feb 3 '15 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.