Universiteit van Amsterdam


Institute for Logic, Language and Computation

15 October 2019, ILLC Lecture, Ronald de Haan

Speaker: Ronald de Haan
Title: Using Computational Complexity in AI
Date: Tuesday 15 October 2019
Time: 11:00
Location: Room F1.15, Science Park 107, Amsterdam


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.