The process of discovery

The other day I taught a reduction from 3SAT to Independent Set, and I learnt a lot from the lecture. I asked the students who had not seen reductions before to come up with it themselves, but I actually had no idea how they could go about it. My question was more like an act of faith than like a lecture plan. I thought to myself as I asked them to find the reduction: "What do I say next if no one has any suggestion? I have no idea." When, as a student, I learned that reduction, it was given to me as if by fiat, and I did not understand how one could come up with such a reduction with no knowledge of gadgets and without having seen any non-trivial reduction before.

But I was wrong to worry. I was delighted to hear many ideas spring up from the room, was careful, to save time, to prune the suggestions that I knew would lead to a dead end, and was very impressed that my class, with no prior experience and in a truly collaborative effort, was able to create all the pieces that combine to make the reduction. I hope that, like me, the students who had seen the reduction before (and who were primarily bystanders in that part of lecture) learned from watching their peers at work.

The first observation that started the discussion was that each variable in a 3SAT assignment is either true or false, with exactly two possibilities, and each vertex in a graph is either in the independent set or not, so, "by analogy", one could try to create one vertex per literal, and, for each variable x, connect the vertex "x is true" to the vertex "x is false" by an edge. The student who suggested that told me that he had never seen it before. It was not reconstructed but created ab nihilho. Impressive! I am singling out that comment because it was the first one and broke the ice, but there were several other equally insightful and creative suggestions from all different students.

The process of discovery is fascinating to watch.