Optional Presentation

Purpose

This exercise deepens both individual and class understanding of NP completeness and how to prove it.

Background

This exercise is based on the ideas of NP completeness presented in sections 34.3 through 34.5 of our textbook. This material will also be covered in lectures between November 12 and December 3.

Be aware, however, that the main material from the presentations you will do for this exercise must come from sources outside of our textbook and class discussion. The sources cited in the “Chapter notes” to chapter 34 of our textbook, particularly those in the first paragraph of the notes, are good places to start.

Activity

Identify some NP complete (or NP hard, or harder) problem not covered in our textbook or class discussions, find and study sources describing it, and give an approximately 15 minute presentation to our class about the problem. Also give me a one to two page written summary of your findings, including a bibliography of sources you consulted.

Presentations and written summaries should minimally include a description of your problem (i.e., what it is) and a summary of the proof that it is intractable. Depending on the problem, you might also include descriptions of approximation algorithms for it, discussions of its real-world applications, or similar things you consider important about it.

I will be happy to meet with you before your presentation to go over drafts of it and of the written summary. You don’t have to do this, but I strongly encourage it—it’s the best way to know ahead of time whether your work is likely to meet the standards for waiving Math 348, and, if not, how you need to improve it; the mere act of giving a presentation isn’t necessarily sufficient.

The presentations and written summaries for this exercise must be prepared and given individually in order to get a waiver for Math 348. You may, however, help one another with the research.

Follow-Up

Please let me know by Tuesday, December 1, if you plan to do this exercise. You can subsequently decide not to present, but I need an upper bound on the number of presentations ahead of time so I know how much class time to reserve for them and how many pre-presentation drafts to expect to review.

We will begin presentations in our December 8 class. If there are more presentations than fit into a single class meeting, we will finish them on December 10. Written summaries are due at the time of your presentation.

Your main reward for doing this exercise is a possible waiver for Math 348, the research and presentation requirement for the math major.

This exercise is completely optional, and carries no direct credit towards Math 303. I do, however, believe that studying an intractable problem in detail will help you understand intractability and therefore do better on the final exam and perhaps the last problem set(s), and that hearing the presentations will improve everyone’s understanding of intractability proofs.