Mercoledý 31-3 14.30

Armando Tacchella, STAR-Lab, DIST, UniversitÓ di Genova.

The NP-hard days of our lives: is there life beyond tractability?

Given P, the class of computational problems solvable in deterministic polynomial time, and NP, the class of computational problems solvable in non-deterministic polynomial time, the fundamental (and still open) question in Computer Science is whether P is a strict subset of NP. Intuitively, the  "P vs. NP" issue relates to our ability of solving efficiently problems that are combinatorial in nature such as the (in)famous Travelling Salesman Problem and other important problems of practical interest. This seminar aims to give a pleasant introduction to the theory of complexity and to motivate why "intractable" problems are a reality that must be faced.
I will try to shed some light on the threshold between tractability and intractability, and I will overview algorithms and tools that manage to tame intractable problems quite effectively. I will conclude with some ideas for further empirical studies of the "P vs. NP" issue.