| Kommentar |
Until today we do not know how to solve NP-complete problems quickly, that is, in polynomial time. In fact, it is a widely accepted assumption that P is not equal to NP, and hence, we assume that we will never be able to find polynomial-time algorithms for these problems. NP-complete problems are considered equivalent up to polynomial time reductions. Nevertheless, their exponential-time properties vary widely.
The lecture covers the most common algorithmic techniques that are employed to solve NP-complete problems significantly faster than via exhaustive search. These techniques include dynamic programming, the inclusion-exclusion principle, measure and conquer, fast subset convolution and local search. These methods are applied to solve problems of strong
practical relevance, such as partition problems, covering and coloring problems, TSP, Hamilton Path, SAT, and many more.
Participants should have a strong interest in theoretical computer science and design and analysis of algorithms. The course is self-contained in the sense that all relevant concepts will be introduced in the lectures. |
