Carleton University - School of Computer Science Honours Project
Winter 2018
The Visualization of Reductions
ABSTRACT
The goal of this honours project was to support students in the formation of a mental
image of how reductions work. To realize this goal an application that visually illustrates
reductions was developed. Each reduction is displayed in the visual format as shown in
the table below. This visual display is meant to align with the actual reduction process
where an input x to problem A is taken and using a map, f, to map that to f(x) which is
then used as input to problem B. A known algorithm to solve problem B, giving solution
y, is then employed. The reverse process of mapping problem B to problem A using
process g is then utilized, which would give the solution g(y) for A on the original input
x. The application displays as many as eight distinct reductions. A small administration
application was built that allows the eight reductions available in the main application
to be hidden/unhidden.
Problem A Problem B
Solution A Solution B
Table 1 - Flow and Format of Reductions Displayed