Demystifying Karp’s 21 Original NP-Complete Problems

The purpose of this research project was to find a simple cycle of reductions among the 21 NP-Complete that Richard M. Karp identified in his paper “Reducibility Among Combinatorial Problems”. To create our cycle, we used Karp’s form of reductions. While we were able to discover several original reductions, we were not able to find a simple cycle among the problems. However, we believe that a simple cycle is still possible, it will just require more time and brain power. ​

Our Team

These are the students working on this project who are a part of Cal Poly Engineerings SURP Program

Jonathan Schreiber


I am a 3rd year Computer Science major at Cal Poly. I am particularly interested in algorithms and technology ethics. It was an honor to work with such bright peers and mentors this summer!

Pranshul Lahkanpal


 am a 3rd year Computer Science major at Cal Poly. I am interested in automating  things with python, regular expressions and algorithms. 

Josie O'Harrow


I am studying mathematics at Oregon State University. In particular, I am interested in number theory, geometry, and theoretical computer science. I have been interested in computer science problems since I started working as a software engineer, but I find the mathematical approach delightful.


We would like to give a big shoutout and thank you to our sponsor, Dr. Theresa Migler, and our colleague, Josie O’Harrow. This project would not have been possible without their guidance and support. 

Our Project's Digital Poster


Share on facebook
Share on twitter
Share on linkedin

Coronavirus Update and Resources