Poslední úprava: prof. Mgr. Zdeněk Dvořák, Ph.D. (21.12.2019)
The series of lectures will provide a tutorial on fine-grained complexity. Fine-grained complexity which emerged over the past decade maps the landscape of problems solvable in polynomial time, and provides insight into their exact asymptotic complexities. By building a formal connection between the complexity of problems like the Longest Common Subsequence and the complexity of solving NP-complete problems such as SAT it provides a plausible explanation why despite lots of effort we did not manage to improve on the trivial quadratic or cubic algorithms for such problems. The course will cover the Strong Exponential Time Hypothesis (SETH) and its variants, problems in P such as Orthogonal Vectors Problem, 3SUM, Longest Common Subsequence and many others, and exhibit a striking relationships between their complexities.
