**Speaker**

Armando Tacchella

STAR-Lab, DIST, University of Genova (Italy)

**Title**

The NP-hard days of our lives (reloaded)

**Abstract**

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.

@LIRA-Home