Demystifying Karp’s 21 Original NP-Complete Problems

  • Computer Science
demystifying_karp
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

researcher

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

Researcher

I  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

Researcher

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.

Acknowledgements

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

Printable Poster (PDF)

Share

Coronavirus Update and Resources

Learn More