Explaining SAT to high school science teachers

Question

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?

Answer 1

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.

Answer 2

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.