TY - JOUR

T1 - COMPUTATIONAL COMPLEXITY of BIASED DIFFUSION-LIMITED AGGREGATION

AU - Bitar, Nicolas

AU - Goles, Eric

AU - Montealegre, Pedro

N1 - Publisher Copyright:
© 2022 Society for Industrial and Applied Mathematics

PY - 2022

Y1 - 2022

N2 - Diffusion-limited aggregation (DLA) is a cluster-growth model that consists of a set of particles that are sequentially aggregated over a two-dimensional grid. In this paper, we introduce a biased version of the DLA model, in which particles are limited to moving in a subset of possible directions. We denote by k-DLA the model where the particles move only in k possible directions. We study the biased DLA model from the perspective of computational complexity, defining two decision problems. The first problem is Prediction, whose input is a site of the grid c and a sequence S of walks, representing the trajectories of a set of particles. The question is whether a particle stops at site c when sequence S is realized. The second problem is Realization, where the input is a set of positions of the grid, P. The question is whether there exists a sequence S that realizes P, i.e., all particles of S exactly occupy the positions in P. Our aim is to classify the Prediction and Realization problems for the different versions of DLA. We first show that Prediction is \bfP - Complete for 2-DLA (thus for 3-DLA). Later, we show that Prediction can be solved much more efficiently for 1-DLA. In fact, we show that in that case, the problem is \bfN \bfL -Complete. With respect to Realization, we show that when restricted to 2-DLA the problem is in \bfP, while in the 1-DLA case, the problem is in \bfL .

AB - Diffusion-limited aggregation (DLA) is a cluster-growth model that consists of a set of particles that are sequentially aggregated over a two-dimensional grid. In this paper, we introduce a biased version of the DLA model, in which particles are limited to moving in a subset of possible directions. We denote by k-DLA the model where the particles move only in k possible directions. We study the biased DLA model from the perspective of computational complexity, defining two decision problems. The first problem is Prediction, whose input is a site of the grid c and a sequence S of walks, representing the trajectories of a set of particles. The question is whether a particle stops at site c when sequence S is realized. The second problem is Realization, where the input is a set of positions of the grid, P. The question is whether there exists a sequence S that realizes P, i.e., all particles of S exactly occupy the positions in P. Our aim is to classify the Prediction and Realization problems for the different versions of DLA. We first show that Prediction is \bfP - Complete for 2-DLA (thus for 3-DLA). Later, we show that Prediction can be solved much more efficiently for 1-DLA. In fact, we show that in that case, the problem is \bfN \bfL -Complete. With respect to Realization, we show that when restricted to 2-DLA the problem is in \bfP, while in the 1-DLA case, the problem is in \bfL .

KW - NL-completeness

KW - P-completeness

KW - computational complexity

KW - diffusion-limited aggregation

KW - space complexity

UR - http://www.scopus.com/inward/record.url?scp=85130586339&partnerID=8YFLogxK

U2 - 10.1137/18M1215815

DO - 10.1137/18M1215815

M3 - Article

AN - SCOPUS:85130586339

SN - 0895-4801

VL - 36

SP - 823

EP - 866

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 1

ER -