<p>Quoting Prof. Avi Wigderson: The “P vs. NP” problem is somewhat like determining “whether intuition can be mechanized” …</p>
<p>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.</p>
<p>Of course, some reductions are much more sophisticated, but I feel that generally the same guideline holds.</p>

CC BY-SA 4.0
2023-09-01T09:43:52.277Z
2023-09-01T13:45:08.427Z
2023-09-01T13:45:08.427Z
Avi Tal
<p>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 <span class="math-container">$P, NP$</span>, reductions, etc means and some algorithmic ideas (they have a strong background in traditional algorithms).</p>
<p>I am currently preparing materials on NP-hardness reductions/gadgets, and I feel most resources just <em>present</em> 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).</p>
<p>I would like to avoid this type of &quot;be smart&quot; solutions when I am presenting the solutions. Are there any resources which spend some time on explaining the <em>intuition</em> of how said gadgets can be created and relevant problem solving skills involved? Unfortunately, I also know a lot of &quot;tricks&quot; from seeing several gadgets, and so it is hard for me to even know what drove me to construct a gadget in said way. &quot;I've seen a similar reduction&quot; is an unsatisfying answer.</p>

CC BY-SA 4.0
2023-09-01T07:53:23.233Z
I actually like the lecture notes by Jonathan Katz (https://www.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.
pizet
CC BY-SA 4.0
2023-09-01T10:49:27.813Z
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.
Hermann Gruber
CC BY-SA 4.0
2023-09-01T14:03:57.287Z
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.
Neal Young
<reductions><np>
Are there complexity teaching resources that do not treat NP-hardness gadgets as Voodoo magic?
user3508551
# Are there complexity teaching resources that do not treat NP-hardness gadgets as Voodoo magic?

(Asked by: username_0 on 2023-08-31)

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.

**Tags:** reductions, np

> **Comments:**
> **username_1**: I actually like the lecture notes by Jonathan Katz (https://www.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.  
> **username_2**: 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.  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_4 on 2023-09-01. Score: 2

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.


---

