Abstract

The class P attempts to capture the efficiently solvable computational tasks. It is full of practically relevant problems, with varied and fascinating combinatorial structure. A line of work that has been gaining a lot of attention attempts to obtain a better understanding of the time complexity of the problems in P by proving reductions between them.

In this talk, I will present the most current landscape of P, summarizing the exciting progress of recent years (most of which will be covered in this workshop). Then, I will highlight directions for future work that are yet to be explored and discuss the challenges that are involved.

Video Recording