Techniques for reducing complexity of algorithms for solving problems with uncertainty and preferences

This project will investigate methods for compiling computations needed to solve combinatorial decision problems with preferences and uncertainty (typically above NP) transforming them into a simpler approximation.

As examples of such methods, one can exploit the preference structure, reducing the size of the problem by pruning away undesirable options, or by fusing options that are similar enough or by simplifying the description language options distinguishable in a more complex language are unified.

Programme : IA certifiable
Thème : Raisonnement automatique et décision

Porteur : Hélène Fargier, DR CNRS, IRIT