5
$\begingroup$

I am teaching a mini-complexity course to high achieving high-school students from my country this fall, and they have all expressed strong interest in learning more about what $P, NP$, reductions, etc means and some algorithmic ideas (they have a strong background in traditional algorithms).

I am currently preparing materials on NP-hardness reductions/gadgets, and I feel most resources just present the gadget, without offering any intuition how that gadget was formed. They mainly spend the time on proving said gadget works (i.e iff proofs).

I would like to avoid this type of "be smart" solutions when I am presenting the solutions. Are there any resources which spend some time on explaining the intuition of how said gadgets can be created and relevant problem solving skills involved? Unfortunately, I also know a lot of "tricks" from seeing several gadgets, and so it is hard for me to even know what drove me to construct a gadget in said way. "I've seen a similar reduction" is an unsatisfying answer.

$\endgroup$
3
  • $\begingroup$ I actually like the lecture notes by Jonathan Katz (cs.umd.edu/~jkatz/complexity/f11). They follow the book of Arora and Barak. But in general I am not sure whether gadgets can presented in a better way. I proved several NP-completeness results myself and the ideas always came out of the blue and are very problem specific. $\endgroup$
    – pizet
    Sep 1, 2023 at 7:53
  • $\begingroup$ In many courses a few such reductions are presented to the students, and then they are expected to do reductions as homework exercises! So it seems to be possible to become a voodoo magician just by observing the voodoo gadgets a few times. $\endgroup$ Sep 1, 2023 at 10:49
  • 3
    $\begingroup$ To teach the concept of reduction, I usually start with problems that are more closely related, where gadgets aren't so tricky. E.g. vertex cover <-> independent set <-> clique. Once they have the basic idea, I start showing reductions from 3-SAT, e.g. to independent set. I show the reduction in stages, start by just trying to model the 2^n assignments with an instance of independent set, then try to figure out how to add the clause constraints... These kinds of reductions seem at least semi-methodical. $\endgroup$
    – Neal Young
    Sep 1, 2023 at 14:03

1 Answer 1

2
$\begingroup$

Quoting Prof. Avi Wigderson: The “P vs. NP” problem is somewhat like determining “whether intuition can be mechanized” …

So, knowing “how we can do” what we do seems rather philosophical. Nevertheless, from my teaching experience, there are some general guidelines that can be followed, such as identifying the dependencies and restrictions in each problem and creating a gadget that will generate similar dependencies and restrictions in both. The 3-SAT to 3-COLOR reduction is a canonical example of this.

Of course, some reductions are much more sophisticated, but I feel that generally the same guideline holds.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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