Grolog/AI event: Iris van Rooij and Tarek Besold

The Tractable Cognition Thesis Revisited

Iris van Rooij
Department of Artificial Intelligence
Donders Institute for Brain, Cognition, and Behaviour
Radboud University Nijmegen, The Netherlands

A central aim of cognitive science is to explain human cognitive capacities. A cognitive capacity is often seen as a mapping of inputs (e.g., sensations, perceptions, concepts, or beliefs) to outputs (e.g., inferences, decisions, plans, or overt responses), and formally defining that mapping is called a computational-level theory of the capacity.  

Given that computational-level theories are underdetermined by data, cognitive scientists can benefit from theoretical constraints on the set of feasible computational-level theories. The Tractable Cognition thesis---which states that cognitive capacities are constrained by tractability---may provide such a constraint. Yet, to utilize this constraint a precise and workable definition of ‘tractability’ is needed.

Traditionally, tractability has been defined as polynomial-time computability, leading to the P-Cognition thesis. As it turns out, however, the P-Cognition thesis is overly restrictive. I therefore propose the FPT-Cognition thesis as an alternative formalization (here, FPT stands for fixed-parameter tractable). In my talk I will discuss the benefits of my proposed formalization, as well as discuss and rebut existing objections to the Tractable Cognition thesis.

---

When Thinking Never Comes to a Halt: Tractability, Kernelization and Approximability in AI

Tarek R. Besold
Department of Cognitive Science
University of Osnabrück, Germany

The recognition that human minds/brains are finite systems with limited resources for computation has led researchers in cognitive science to advance the Tractable Cognition thesis (originally spearheaded by Iris van Rooij): Human cognitive capacities are constrained by computational tractability. As also artificial intelligence (AI) in its attempt to recreate intelligence and capacities inspired by the human mind is dealing with finite systems, transferring this thesis and adapting it accordingly may give rise to insights that can help in progressing towards meeting the goals of AI. We therefore developed the ``Tractable Artificial and GeneraI Intelligence Thesis'' by applying notions from parametrized complexity theory and approximation theory to a general AI framework, also showing connections to recent developments within cognitive science and to long-known results from cognitive psychology.

In this talk, I will first introduce the Tractable AGI Thesis and showcase a worked application example highlighting its usefulness, namely an in-depth analysis of the Heuristic-Driven Theory Projection framework for computational analogy-making. In the second (more speculative) part, I will present some initial thoughts on how the Tractable AGI Thesis and the corresponding paradigm can be connected to the notion of heuristics and their application in AI frameworks.