Abstract: In this talk, we will take a guided tour through the landscape of computational problems that go beyond classical NP. While NP-complete problems are already challenging, many real-world reasoning tasks - such as model counting, inference, or strategic decision-making - reside higher in the polynomial hierarchy and demand even greater computational effort.

We will begin by revisiting the foundations of NP-hard problem solving, and then extend our focus to problems in the second level of the polynomial hierarchy. A particular emphasis will be placed on model counting (#P-complete problems), which plays a central role in probabilistic reasoning, verification, and AI.

To address these complex problems, we will explore the use of advanced algorithmic frameworks including knowledge compilation and SAT-based solving techniques. We will highlight how these techniques help bridge the gap between theoretical hardness and practical solvability, enabling efficient reasoning even in domains that formally lie beyond NP.

Jean-Marie Lagniez is a Professor of Computer Science at Artois University and a researcher in artificial intelligence, specializing in automated reasoning, satisfiability solving, and explainable AI. His work focuses on the intersection of logic, algorithms, and machine learning, with significant contributions to model counting, SAT-based techniques, and abductive reasoning. He has published extensively on preprocessing methods, solving strategies, and explanation generation, particularly in the context of CNF-based representations and tree ensemble classifiers. Jean-Marie is actively involved in bridging theoretical foundations with practical applications in AI reasoning systems.