Mercoledì 31-3 14.30
Armando Tacchella, STAR-Lab, DIST, Università di Genova.
Title
The NP-hard days of our lives: is there life beyond tractability?
Abstract
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.