Infinite Separation between General and Chromatic Memory

Alexander Kozachinskiy

Introduction

In the theoretical study of reactive systems, interactions between a controller and its environment are often modeled as two-player infinite games played on directed graphs, known as arenas. In these games, a player (the Protagonist) aims to satisfy a specific winning condition by choosing moves based on the history of the play. A fundamental metric for evaluating the complexity of these strategies is the amount of memory required to win.

This paper addresses a long-standing open question in the theory of infinite games: the relationship between "general" and "chromatic" memory. While it was known that these two types of memory are not identical, previous research had only identified finite gaps between them. This work provides a definitive resolution by demonstrating that the separation between general and chromatic memory can be infinite.

Defining Memory: General vs. Chromatic

To understand the significance of this result, one must distinguish between how a strategy perceives the game's history:

  1. General Memory (Edge-Aware): The strategy has access to the sequence of edges traversed in the graph. This provides the player with the full structural context of the arena, allowing them to know exactly which node they currently occupy.
  2. Chromatic Memory (Color-Blind): The strategy only observes the sequence of colors assigned to the edges. It is "blind" to the underlying graph structure; if two different paths produce the same sequence of colors, a chromatic strategy cannot distinguish between them.

For years, the field sought to determine if general memory was always as efficient as chromatic memory. Specifically, researchers led by Kopczyński questioned whether a winning condition that is "easy" (finite-state) for general memory could be "impossible" (infinite-state) for chromatic memory.

The Rope Ladder Construction

The author proves the infinite separation by introducing a novel winning condition termed the "Rope Ladder" (RL). This condition is defined over an infinite partially ordered set (poset) $\Omega$ that resembles two parallel vertical ladders.

The game can be visualized as an "ant" moving along this ladder. Each move in the game corresponds to a function (a color) applied to the ant's current position. The winning condition is a safety-like requirement: the ant must never exceed a specific height or "layer" on the ladder.

The Power of Context

The core of the proof lies in how information is filtered through the two memory types:

  • Upper Bound (General Memory): The author demonstrates that just two states of general memory are sufficient to win the Rope Ladder game. By knowing the current node (the context), the player can use these two states to track the maximal possible positions of the ant and ensure it stays within the allowed bounds. This uses a combination of König's Lemma and the analysis of "irregular plays."
  • Lower Bound (Chromatic Memory): Conversely, the author proves that no finite amount of chromatic memory is sufficient. Using a combinatorial argument involving "Q-indistinguishable" binary words and XOR sums, the author constructs specific arenas where any chromatic strategy eventually loses track of the ant's exact position. Because the strategy cannot distinguish between different paths that yield the same color sequence, it eventually makes a move that pushes the ant beyond the winning threshold.

Key Results and Theoretical Significance

The primary contribution of this paper is Theorem 1: There exists a winning condition $W$ over a finite set of colors such that the general memory complexity is exactly 2 ($\text{GenMem}(W) = 2$), but the chromatic memory complexity is infinite ($\text{ChrMem}(W) = +\infty$).

Several aspects of this result are particularly noteworthy:

  • Finite Color Set: The infinite separation is achieved using a small, finite set of only five colors.
  • Borel Hierarchy: The Rope Ladder condition is situated at the $\Sigma^0_2$ level of the Borel hierarchy. This indicates that infinite separation is not a property reserved for highly complex conditions but can occur in relatively simple types (infinite unions of safety conditions).
  • Resolution of Kopczyński’s Question: The paper provides a definitive "No" to the hypothesis that general and chromatic memory requirements are always comparable or equal.

Conclusion and Future Directions

By proving that knowing the path (the edges) is fundamentally more powerful than merely knowing the labels (the colors), this paper shifts the understanding of strategy complexity in graph games. However, the discovery of this infinite gap opens new avenues for research:

  1. Safety Conditions: Can this infinite gap be found in a pure safety condition (a closed set in the Borel hierarchy), or is the $\Sigma^0_2$ complexity of the Rope Ladder a requirement?
  2. Prefix Independence: Does this separation persist for prefix-independent conditions, where the winning status of a play is unaffected by any finite initial sequence of moves?
  3. Antagonist Complexity: While the Protagonist's memory requirements are now understood for this condition, the memory complexity for the Antagonist remains an open question.

Reference: Kozachinskiy, A. (2023). Infinite separation between general and chromatic memory. arXiv:2208.02691v2 [cs.GT].

Summary updated

Abstract

In this note, we answer a question from [Alexander Kozachinskiy. State Complexity of Chromatic Memory in Infinite-Duration Games, arXiv:2201.09297]. Namely, we construct a winning condition $W$ over a finite set of colors such that, first, every finite arena has a strategy with 2 states of general memory which is optimal with respect to $W$, and second, there exists no $k$ such that every finite arena has a strategy with $k$ states of chromatic memory which is optimal with respect to $W$.
BibTeX
@inproceedings{kozachinskiy2022infinite,
  author = {Alexander Kozachinskiy},
  title = {{Infinite Separation between General and Chromatic Memory}},
  booktitle = {LATIN},
  year = {2022},
  doi = {10.1007/978-3-031-55601-2\_8},
}
Figure