Computational Complexity of Segmentation

Federico Adolfi, Todd Wareham, Iris van Rooij

Introduction: The Challenge of Sequence Segmentation

Cognitive systems are tasked with parsing continuous, dynamic streams of information—such as speech, music, or visual events—into discrete, meaningful chunks. This fundamental process, known as segmentation, is a prerequisite for higher-level cognition. Within cognitive science and neuroscience, it is widely assumed that segmentation is a computationally intractable problem due to the "combinatorial explosion" of possible boundary placements as sequence length increases.

Figure 1: Decomposition of cognitive capacity into segmentation and downstream processing across various sequence domains.

Because of this perceived hardness, many theories suggest that the brain must rely on specific biological or environmental constraints—such as top-down predictive biases or strict neural integration windows—simply to make the problem solvable. This paper investigates whether these assumptions of computational intractability are mathematically justified.

Methodology: Formalization and Search Space Analysis

The authors formalize segmentation at Marr’s computational level as an optimization problem. Given a sequence of length $N$ and a "scoring function" that evaluates the quality of any potential segment, the goal is to find a partition of disjoint segments that spans the entire sequence while maximizing the total score.

Using analytic combinatorics, specifically generating functions for integer compositions, the authors analyzed the growth rate of the search space. They found that the number of possible segmentations grows exponentially with sequence length $N$. For an unconstrained sequence, there are $2^{N-1}$ possible ways to place boundaries. Even when imposing constraints like minimum or maximum segment sizes, the search space remains exponentially large.

Proving Tractability via Graph Reduction

To determine the actual computational complexity, the authors employed polynomial-time reduction. They mapped the segmentation problem onto an interval graph. In this representation, each node represents a possible valid segment, and edges connect segments that overlap in time.

Figure 6: Mapping segments (left) to a graph structure (right) to analyze computational complexity.

The problem of finding the optimal segmentation is reduced to finding a "Minimum-Weight Independent Dominating Set" on this graph. While this problem is NP-hard for arbitrary graphs, it is solvable in polynomial time for interval graphs. Specifically, the algorithm to construct the segment graph runs in $O(N^4)$ time, and solving the dominating set problem on the resulting interval graph is also polynomial.

Key Insights and Results

The core finding of this research is a challenge to cognitive science intuition: an exponentially large search space does not necessarily imply computational intractability.

  • Exponential Search Space (Theorems 1-3): The number of possible segmentations grows exponentially, regardless of whether segments are bounded in size.
  • Computational Tractability (Theorem 4): Despite the exponential search space, the unconstrained segmentation problem is polynomial-time computable.
  • Theoretical Re-evaluation: If segmentation is inherently tractable, the brain does not require constraints like neural oscillations or bottom-up cues just to make the task possible. Instead, these mechanisms likely serve to improve the accuracy or relevance of the segments for specific tasks.

Conclusion and Future Directions

This theoretical analysis suggests that researchers should redirect their focus. Rather than searching for biological constraints that "solve" the combinatorial explosion, future empirical work should investigate how neural and environmental regularities guide the system toward optimal boundary placements. While this model assumes a one-dimensional sequence, future work may explore whether high-dimensional, parallel input streams (e.g., simultaneous audio-visual processing) maintain these tractability properties.

Summary updated

Abstract

Author(s): Adolfi, Federico; Wareham, Todd; van Rooij, Iris | Abstract: Computational feasibility is a widespread concern that guides the framing and modeling of biological and artificial intelligence. The specification of cognitive system capacities is often shaped by unexamined intuitive assumptions about the search space and complexity of a subcomputation. However, a mistaken intuition might make such initial conceptualizations misleading for what empirical questions appear relevant later on. We undertake here computational-level modeling and complexity analyses of segmentation - a widely hypothesized subcomputation that plays a requisite role in explanations of capacities across domains - as a case study to show how crucial it is to formally assess these assumptions. We mathematically prove two sets of results regarding hardness and search space size that may run counter to intuition, and position their implications with respect to existing views on the subcapacity.
BibTeX
@inproceedings{adolfi2022computational,
  author = {Federico Adolfi and Todd Wareham and Iris van Rooij},
  title = {{Computational Complexity of Segmentation}},
  booktitle = {CogSci},
  year = {2022},
  url = {https://openreview.net/forum?id=oGa788BrxF},
}
Figure