After defining the notion of algorithmic hardness, the methods for solving hard problems are systematically presented. For each design method we analyze its limits and its guarantees with respect to solution quality and efficiency.

This course unit looks into algorithmic approaches to the solving of hard problems, particularly with moderately exponential-time algorithms and parameterized algorithms.The seminar is accompanied by a comprehensive reflection upon the significance of the approaches presented for computer science tuition at high schools.

The main goal of the complexity theory is t to classify computing problems with respect to their hardness. The complexity theory develops methods and proof techniques for establishing lower and upper bounds on the complexity of concrete problemsand for investigating the fundamental propeties of abstract complexity measures and computing models.