• We establish a progressive partitioning model of granular computing, providing a set-theoretic framework that connects ground granules, composite granules, and hierarchical granular structures. • We propose a general axiomatic framework for complexity measures of progressive partitions, extending the classical complexity measures of sets and partitions to multi-level granular structures. • We investigate a class of interaction-based complexity measures, demonstrating the conceptual differences between complexity and granularity in granular computing. One of the claims regarding the power of granular computing is the computational efficiency and practical applicability in solving complex problems. The majority of discussions supporting this claim are typically made based on intuitive arguments or through examples by equating the complexity and the granularity of granules and granular structures. In 2019, Matthew Yao (Knowledge-Based Systems 163 (2019) 885–897) argued that the granularity and complexity are two related but different concepts. For quantifying the complexity, he proposed a class of interaction-based measures. Unfortunately, this direction of research has not received its due attention. To further promote theoretical studies on the concept of the complexity in granular computing, in this paper, we conduct an in-depth and systematic analysis of complexity measures in a progressive partitioning model of granular computing. By taking interactions among components as the underlying notion for explaining the complexity of problem-solving using granular computing, we investigate a class of interaction-based complexity measures. As a step towards systematic research in pursuit of a deeper understanding of the fundamental notion of complexity in granular computing, we move beyond intuitive arguments and aim at a sound theoretical foundation.
Li et al. (Wed,) studied this question.