Polynomiality for understanding and extending the limits of efficient solvers.

The partners of this project are IRIT, LSIS, Greyc and CRIL. The TUPLES project focuses on the effective solution of NP-complete problems, in particular in the field of artificial intelligence. The main objective is to significantly push back the limits currently observed on the efficiency of combinatorial problem solvers, while at the same time establishing a theoretical framework that seems necessary to reach this objective. The TUPLES project addresses this issue by developing and exploiting polynomial classes and by considering them as analytical tools to explain the relative efficiency of solvers. White program 2010-2014.


Scientific Responsible for CRIL :
Lakhdar Saïs
Participants :
Daniel Le Berre
Pierre Marquis
Bertrand Mazure
Duration :
2010-2015