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.

Peer-Reviewed

Yes

Document Type

Journal Article

Included in

Engineering Commons

Share

COinS