Redux: An Interactive, Dynamic Knowledge Base for Teaching NP-completeness

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-and-pencil 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. We present an open-source web app called Redux that provides a dynamic interactive user interface atop a practical knowledge base 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 knowledge base extensible, allowing students to contribute and compare their reductions and solutions to those already available. Two surveys were administered, with respondents overwhelmingly indicating that Redux helped them to better understand mapping reductions; that they would prefer using Redux to solve similar problems manually; and that Redux makes learning NP-complete reductions more enjoyable. Redux is accessible online via https://redux.portneuf.cose.isu.edu/.