Classifying the Arithmetical Complexity of Teaching Models

Achilles A. Beros, Ziyuan Gao, Sandra Zilles

Abstract

This paper classifies the complexity of various teaching models by their position in the arithmetical hierarchy. In particular, we determine the arithmetical complexity of the index sets of the following classes: (1) the class of uniformly r.e. families with finite teaching dimension, and (2) the class of uniformly r.e. families with finite positive recursive teaching dimension witnessed by a uniformly r.e. teaching sequence. We also derive the arithmetical complexity of several other decision problems in teaching, such as the problem of deciding, given an effective coding of all uniformly r.e. families, whether or not the teaching dimension of a specific set with respect to a family is upper bounded by a given value.

Introduction

In computational learning theory, the standard paradigm often focuses on the learner's ability to identify a concept from a stream of data. Algorithmic teaching reverses this perspective, asking instead: can a "teacher" select a minimal, optimized set of examples to force a learner to identify the correct concept?

While several models exist to quantify this—most notably the Teaching Dimension (TD) and the Recursive Teaching Dimension (RTD)—their "descriptive complexity" remained largely unmapped. This research addresses that gap by placing these models within the arithmetical hierarchy, a classification system in mathematical logic that ranks the complexity of statements based on the number of alternating quantifiers (e.g., "for all" $\forall$ and "there exists" $\exists$) required to define them.

Methodology

The study utilizes techniques from Computability Theory, specifically focusing on uniformly recursively enumerable (u.r.e.) families. These are collections of sets where each set can be systematically listed by a computer program.

To determine the complexity of various teaching properties, the authors employ many-one reductions. This method involves taking a known "hard" problem from the arithmetical hierarchy (such as determining if a set is cofinite) and demonstrating that it can be transformed into a teaching decision problem. If such a transformation is possible, the teaching problem is proven to be at least as complex as the reference problem. This allows the authors to establish "completeness" results at various levels of the hierarchy, such as $\Sigma^0_5$-completeness.

Key Insights and Theoretical Contributions

The Complexity Gap

One of the paper's most significant findings is the massive jump in logical depth when moving from individual sets to entire families. Deciding if a single set within a family has a finite teaching set is relatively straightforward, placing it at the $\Pi^0_2$ level. However, deciding if the entire family possesses a finite teaching dimension is significantly more difficult, reaching the $\Sigma^0_5$ level. This suggests that the global property of "teachability" for a family is exponentially more complex to verify than the local property for a single concept.

The Collapse of XTD for Infinite Families

A surprising result involves the Extended Teaching Dimension (XTD). The authors prove that for u.r.e. families, having a finite XTD is logically equivalent to the family itself being finite. This causes the complexity of XTD to collapse to the $\Sigma^0_3$ level, making it an extremely restrictive model for infinite collections of sets.

The "Tell-Tale" Connection

The research bridges the gap between modern teaching models and classical learning theory. By building on Dana Angluin’s foundational work regarding "tell-tale" sets—which are essential for Gold-style learning in the limit—the authors demonstrate how these classical concepts underpin the structural requirements of algorithmic teaching.

Summary of Results

The following table summarizes the arithmetical complexity of deciding various teaching properties within u.r.e. families:

Property to Decide Arithmetical Complexity
Distinguishing Set (DS): Does set $D$ distinguish set $L$ from others? $\Pi^0_2$-complete
Extended Teaching Dimension (XTD): Is the XTD finite? $\Sigma^0_3$-complete
Universal TD: Do all members of the family have finite TD? $\Pi^0_4$-complete
Recursive Teaching Dimension (RTD+): Is the RTD finite? $\Sigma^0_4$-complete
Teaching Dimension (TD): Is the overall TD of the family finite? $\Sigma^0_5$-complete

These results suggest a philosophical trend: as teaching models become more "cooperative" or involve recursive sequences, the logical formulas required to define their boundaries become increasingly complex.

Limitations and Future Directions

While this work provides a rigorous map of the complexity landscape, several questions remain:

  1. Scope of Families: The results are specific to u.r.e. families. The complexity may shift for families that lack a clean, uniform numbering system.
  2. The RTD Gap: While variants like the "positive" and "semi-effective" RTD were classified, the complexity of the original, standard RTD model remains an open problem.
  3. Numbering Systems: Future research could investigate whether "one-one numberings" (where each set has a unique identifier) simplify the classification compared to standard numberings where multiple indices can represent the same set.

Summary updated

Abstract

This paper classifies the complexity of various teaching models by their position in the arithmetical hierarchy. In particular, we determine the arithmetical complexity of the index sets of the following classes: (1) the class of uniformly r.e. families with finite teaching dimension, and (2) the class of uniformly r.e. families with finite positive recursive teaching dimension witnessed by a uniformly r.e. teaching sequence. We also derive the arithmetical complexity of several other decision problems in teaching, such as the problem of deciding, given an effective coding $\{\mathcal L_0,\mathcal L_1,\mathcal L_2,\ldots\}$ of all uniformly r.e. families, any $e$ such that $\mathcal L_e = \{L^e_0,L^e_1,\ldots,\}$, any $i$ and $d$, whether or not the teaching dimension of $L^e_i$ with respect to $\mathcal L_e$ is upper bounded by $d$.
BibTeX
@inproceedings{beros2016classifying,
  author = {Achilles A. Beros and Ziyuan Gao and Sandra Zilles},
  title = {{Classifying the Arithmetical Complexity of Teaching Models}},
  booktitle = {ALT},
  year = {2016},
  url = {https://openreview.net/forum?id=KVO0l7FNxr},
}
Figure