Computation Theory

The P vs NP problem has substantial implications in a variety of fields outside of computer science. Natural science, logistics, language, games, national security, and many other fields have NP-Complete problems that stymie research efforts and prevent breakthroughs.

With a small group, you will produce a 10 minute presentation for class on Monday, April 11, on an NP-Complete or NP-Hard problem that impacts a field you care about.

Getting Started

Wikipedia has a list of NP-Complete problems Here.

If you can't find an interesting one, feel free to ask about some options.

Feel free to treat wikipedia as a valid resource for this project, but try to verify any claims with other sources as well.

I'm requiring that presentations cover the following topics.

• The problem description (what the problem is). Please go into depth on this point, and include information about what input it expects.
• A detailed example of the problem, including an example solution.
• The process of verifying the solution (if there is a process)
• Is there an approximate solution? What are its drawbacks?
• An example of how the problem impacts a field you care about. You should also talk about what would change in the world if the problem were solvable in polynomial time.

Submitting your Work

Come to class on Monday ready to give your presentation as a group.