Armando Tacchella
STAR-Lab, DIST, University of Genova (Italy)
The NP-hard days of our lives (reloaded)
One important open question in Computer Science is the issue of whether NP, i.e., the class of problems solvable in non-deterministic polynomial time, is a proper superset of P, i.e., the class of problems solvable in deterministic polynomial time. The issue is not just an intriguing exercise for theoretical computer scientists, but it has to do with our ability to discover efficient algorithms for combinatorial problems which, as of today, can be solved only by resorting to algorithms whose worst-case run time on deterministic, i.e., real, machines is exponential. The purpose of the seminar is to briefly introduce the theory of NP-completeness and the equivalence class of NP-complete problems as a candidate set for (NP - P). We also mention some of the more interesting NP-complete problems that have also a starking practical relevance, among which the problem of discovering whether a formula in Boolean logic admits at least one satisfying assignment, a.k.a., the SAT problem. We then concentrate on SAT to show what we believe to be a viable approach to solve a general class of problems in a robust and efficient way. The framework proposed is based on the concept of "emergent reasoner", i.e., a set of hand-coded and/or automatically synthesized modules, each one devoted to fulfill a specific (basic) task and cooperating with the others: the reasoner evolves according to adaptive patterns that are learned through experience in solving instances. The ultimate goal of this research is to make the question of P vs. NP irrelevant in the practice of SAT, by being able to tackle efficiently any SAT instance.