15 October 2019, ILLC Lecture, Ronald de Haan

Abstract:

Combinatorial problems occur in many areas of artificial intelligence, e.g., in problem solving, planning, knowledge representation and reasoning, and multi-agent systems. Solving such problems typically comes with extremely high computational costs, which poses a significant obstacle for developing high-quality AI systems. In order to advance artificial intelligence methods, it is important to solve these problems with only a limited amount of computational resources. The mathematical theory of computational complexity can be used as an important tool for developing various algorithmic methods to solve such hard combinatorial problems in AI. In this talk, I will discuss in what ways computational complexity can be used to guide AI research and the development of algorithmic tools in various areas of AI. I will do so using three case studies from different areas of AI.