Why Is Symbolic Reasoning Computationally Hard?

Introductory Course at the 4th European Summer School on Artificial Intelligence

by Andreas Pieris (University of Cyprus & University of Edinburgh)

Overview

Symbolic reasoning is a process of manipulating symbols and abstract representations to draw conclusions. It involves using structured knowledge, such as rules and facts, to perform logical operations and derive new information. On the other hand, sub-symbolic reasoning is a method that uses patterns and statistical learning from data to make decisions, rather than explicit, human-defined logical rules.

There is a consensus that the key advantage of symbolic reasoning, compared to sub-symbolic reasoning, is its transparency and explainability as the reasoning process can be traced through the logical rules. However, this advantage comes at a high price, that is, symbolic reasoning is in general computationally expensive.

The goal of this course is to perform a thorough computational complexity analysis, using formal tools from computability and complexity theory, with the aim of explaining the key reasons why symbolic reasoning with logical rules is computationally hard. In particular, we will show that reasoning with arbitrary logical rules is algorithmically an unsolvable problem. We will further show that, even if we severely restrict the syntax of the logical rules, symbolic reasoning remains computationally very hard.

A key characteristic of this course is its self-contained nature as all the technical tools that will be used to perform the aforementioned complexity analysis will be properly introduced.

Course Outline

Lecture 1: Reasoning with Rule-based Knowledge Bases (slides, lecture)

Syntax and semantics of knowledge bases based on existential rules
Formalize reasoning with rule-based knowledge bases
The main reasoning algorithm (restricted or standard chase)

Lecture 2: Undecidability of Reasoning with Rule-based Knowledge Bases (slides, lecture)

Introduce the necessary tools from computability theory (Turing machines, reductions)
Show that reasoning with rule-based knowledge bases is undecidable

Lecture 3: Reasoning with Knowledge Bases based on Full (Existential-free) Rules (slides, lecture)

Introduce full (existential-free) rules and discuss some of their applications
Introduce the necessary tools from complexity theory (time complexity classes, polynomial time reductions)
Show that reasoning with knowledge bases based on full rules is solvable in exponential time
Show that exponential time is the best that we can hope for, that is, the problem is hard for EXPTIME

Lecture 4: Reasoning with Knowledge Bases based on Linear Rules (slides, lecture)

Introduce linear rules and discuss some of their applications
Introduce the necessary tools from complexity theory (non-deterministic Turing machines, space complexity classes)
Show that reasoning with knowledge bases based on linear rules is solvable using polynomial space
Show that polynomial space is the best that we can hope for, that is, the problem is hard for PSPACE

Note: The lectures were scheduled for 90 minutes. However, all the lectures ran a bit over time, and thus, the last few minutes were not recorded.

Prerequisites and Target Audience

The key characteristic of this course is its self-contained nature. All the technical tools needed for the complexity analysis that will be performed throughout the course will be properly introduced. Rudimentary knowledge of relational databases and first-order logic is desirable but not necessary.

The proposed course is intended for senior undergraduate and graduate students with basic knowledge of discrete mathematics (familiarity with the concept of mathematical proof and basic notions such as sets and functions). The course will appeal to students that are interested in the broader area of symbolic AI, and in particular in the principles of knowledge representation and reasoning.

Page updated

Google Sites

Report abuse