| Whereas interactive dynamic visualization tools have been successfully developed and used for teaching some topics in computational theory (CT), there remains a noticeable lack of such tools for teaching NP-completeness which continues to be widely taught using paper-andpencil methods. Despite its important theoretical and practical value, NP-completeness—and mapping reductions in NP-completeness in particular—tends to be a challenging concept for CT students to understand. This thesis represents work on an open-source web app called Redux that provides a dynamic interactive user interface atop a practical knowledgebase of NP-complete problems, reductions, and solution algorithms. A key feature of the interface is the visualization of arbitrary problem instances, mapping reductions, solutions, and gadgets—including those reachable via transitivity. The web app is designed to make the knowledgebase extensible, allowing students to contribute and compare their own reductions and solutions to those already available. We describe Redux’s development and highlight the first prototype of the tool. Two surveys were administered, with respondents overwhelmingly indicating that Redux helped them to better understand mapping reductions; that they would prefer using Redux to solving similar problems manually; and that Redux makes learning NP-complete
reductions more enjoyable. Finally, we discuss how the principles of computational creativity and NP-completeness can be unified in extending many-one reducibility to a popular flood-fill game called KAMI. By rendering NP-complete problems as puzzles, we can unlock the KAMI player-base to crowd-source and solve real-world NP-complete problems. Such a concept serves as a reminder of the importance of NP-completeness in education. Redux is accessible online via https://redux.portneuf.cose.isu.edu/. |