Complexity of the freezing majority rule with L-shaped neighborhoods

In this article we investigate the computational complexity of predicting two dimensional freezing majority cellular automata with states {−1,+1}, where the local interactions are based on an L-shaped neighborhood structure. In these automata, once a cell reaches state +1, it remains fixed in that state forever, while cells in state −1 update to the most represented state among their neighborhoods. We consider L-shaped neighborhoods, which mean that the vicinity of a given cell c consists in a subset of cells in the north and east of c. We focus on the prediction problem, a decision problem that involves determining the state of a given cell after a given number of time-steps. We prove that when restricted to the simplest L-shaped neighborhood, consisting of the central cell and its nearest north and east neighbors, the prediction problem belongs to NC, meaning it can be solved efficiently in parallel. We generalize this result for any L-shaped neighborhood of size two. On the other hand, for other L-shaped neighborhoods, the problem becomes P-Complete, indicating that the problem might be inherently sequential.