Computational complexity of biased diffusion-limited aggregation
Artículo
Open/ Download
Access note
Acceso abierto
Publication date
2022Metadata
Show full item record
Cómo citar
Bitar Varleta, Nicolás Sergio
Cómo citar
Computational complexity of biased diffusion-limited aggregation
Abstract
Diffusion-Limited Aggregation (DLA) is a cluster-growth model that consists in 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 move 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 Prediciton and Realization problems for the different versions of DLA. We first show that Prediction is P-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 NL-Complete. With respect to Realization, we show that restricted to 2-DLA the problem is in P, while in the 1-DLA case, the problem is in L.
Patrocinador
CONICYT-PFCHA/MagisterNacional/2019 22190497
Comision Nacional de Investigacion Cientifica y Tecnologica (CONICYT)
CONICYT FONDECYT 1200006
11190482
ANID via PAI + Convocatoria Nacional Subvencion a la Incorporacion en la Academia Ano 2017 PAI77170068
Indexation
Artículo de publícación WoS
Quote Item
SIAM Journal on Discrete Mathematics Volume 36 Issue 1 Page 823-866 Published 2022 Indexed 2022-04-20
Collections
The following license files are associated with this item: