Students attending the course can do an optional presentation about a proof of NP-hardness or NP-completeness, in front of the class. The presentation must be in English and all the other students presenting must also attend their colleague presentation. All this will happen during the course, hopefully in a single week. Think about a 20-25 minute per presentation at the blackboard: for time constraints, I will be forced to abruptly interrupt presentations that take too long.

The presentation must:

• describe the problem precisely
• present the proof

please prepare well, use notes if needed, rehearse a bit in advance, but do not recite by heart.

Evaluation of the intermediate presentation: the problem to be presented can be selected from a list that I will provide. Students are free to decide the reduction and bibliographic source they prepare the presentation from. Of course not all reductions are equal, and a trivial reduction will contribute less to the grade than a more complex one. Anyway, I suggest avoiding artificially complicated reductions.

Students can propose other problems to present, and in that case I may consider the suggestion and give permission.