Title

VISUALIZING NP-COMPLETENESS THROUGH CIRCUIT-BASED WIDGETS

Authors

Steven R. Vegdahl, University of PortlandFollow

Journal Title

Journal of Computing Sciences in Colleges

Publication Date

2016

Abstract

The concept of intractability is an important one in a CS curriculum. Students should know that some problems are computationally infeasible; ideally, they should have the ability to examine a problem and determine whether it is intractable. This paper presents two widgets that help students gain better intuition about NP-completeness. Each maps circuit satisfiability to a target problem in a visually intuitive way.

Author Supplied Keywords

Computer science--Study and teaching; Computational complexity

Publication Information

Journal of Computing Sciences in Colleges, 2016, Volume 31, Issue 3, 201-209.

© 2014 by the Consortium for Computing Sciences in Colleges

Archived version is final published version.

Citation: Pilot Scholars Version (Modified MLA Style)

Vegdahl, Steven R., "VISUALIZING NP-COMPLETENESS THROUGH CIRCUIT-BASED WIDGETS" (2016). Engineering Faculty Publications and Presentations. 28.
https://pilotscholars.up.edu/egr_facpubs/28

Peer-Reviewed

Yes

Document Type

Journal Article