P7: Intractability

This session is the last problem session of the course. It is about intractability.

The theoretical tools we use/revise are:

• decision problems in P/NP,
• polynomial-time reductions
• NP-completeness.

We solve some problems from the EDA ProblemSet, section 7 Intractability.

After class

To test your understanding, try exercises from the Collection of Solved Exams. For instance:

• 13/01/2020 Final EDA Exam Problem 4
• 09/06/2020 Final EDA Exam Problem 4A-4B
• 08/01/2021 Final EDA Exam Problem 3
• 07/06/2021 Final EDA Exam Problem 1.b
• 16/01/2023 Final EDA Exam Problem 4
• 08/01/2024 Final EDA Exam Problem 4