1. Introduction
Motivation. A
majority automata can be defined as a two-state cellular automata (namely with states
and
where in each synchronous step, each site takes the most represented state in its neighborhood. The majority rule is one of the simplest defined rules, and appears naturally in models from physics, biology, social phenomena, and elections systems [
1,
2,
3,
4,
5,
6] For that reason, a common task consists of computationally simulating the dynamics that arise given an initial finite configuration. A natural question asks what are the most efficient algorithms that can be implemented in order to compute the state configuration reached at a given time-step. This problem is known as the
prediction problem.
The computational complexity of a computational task can be defined as the amount of resources, such as time or space, needed to solve it. One fundamental set of computational decision problems is the class P, which is the class of problems solvable in polynomial time on a deterministic Turing machine. The class P is informally known as the class of problems that admit an efficient algorithm.
Evidently, the prediction problem can be solved by simply simulating the dynamics of the cellular automata for the given number of time-steps. This is called the
trivial algorithm. In [
7] Goles et al. showed that the dynamics of the majority automaton reaches an attractor in a number of time-steps that is linear in the size of the configuration. Moreover, the reached attractor is either a fixed-point or a limit cycle of period two. This result implies that the prediction problem can be solved in polynomial time. Therefore, if we aim to solve the prediction problem more efficiently than the trivial algorithm, we would have to classify it in a proper subclass of
P.
The class of non-deterministic logarithmic space problems
NL is the class of decision task solvable by a non-deterministic logarithmic-space Turing machine. It is known that
, and it is a widely believed conjecture that the inclusion is proper. The problems in
P that are the most likely to not belong to
NL are the
P-Complete problems, to which any other problem in
P can be reduced by a logarithmic-space reduction. If we could show that some
P-Complete problem belongs to
NL, we would deduce that
[
8,
9].
An example of a
P-Complete problem is the circuit value problem (CVP), which consists of determining the output of a given circuit with a particular configuration. Further, the monotone circuit value problem (MCVP), i.e., only considering the gates AND and OR, is also
P-Complete. Intuitively, circuits are hard to compute quickly because in order to compute a given layer of gates, it is necessary to know the state of the previous ones. For a deeper understanding of circuit complexity, see [
10,
11,
12].
In [
9], Moore studied the computational complexity of the majority automata in a
d-dimensional lattice. He showed that in three or more dimensions, the prediction problem is as hard as evaluating monotone circuits, which implies that the prediction problem is
P-Complete. Roughly speaking, this means that in order to compute the state in a given site, the best option is to simulate the dynamics of the automaton until it reaches an attractor. However, Moore suggested that in two dimensions with von Neumann neighborhood, it would be possible to predict the dynamics much more efficiently.
The proof of
P-completeness given in [
9] consists of a series of three dimensional
gadgets used to simulate the different parts of a monotone circuit. While it is easy to generalize these gadgets to more than three dimensions, the restriction to two dimensions seems a much more (or even impossible) task. In fact, one of the main difficulties is that the two-dimensional grid is a planar graph. The
planar monotone circuit value problem (PMCVP) is the restriction of MCVP to planar circuits. In [
13], it is shown that PMCVP belongs to the class
NC. This class of problems are widely believed to be properly included in
P. In addition, it contains the class
NL. Therefore, intuitively, a proof of
P-completeness of the two-dimensional majority should somehow manage to simulate wire crossings in a planar topology.
In the same article, Moore also studied the
biased majority automata (called
half-or-more automata [
9]), which corresponds to the majority automata where the sites do not consider their own state in the neighborhood, and privilege state 1 in tie cases. Moore stated that the prediction problem for non-strict majority automaton is
P-Complete in three or more dimensions, and also conjectured that in two dimensions, the problem should be solved more efficiently.
Heterogeneous majority. In this article, we study the prediction problem on a non-homogeneous setting. We ask for the computational complexity the non-homogeneous cellular automata that combine cells having the majority rule (which in the following we call stable majority rule) and cells having the biased majority rule. Such automata are called the heterogeneous majority cellular automata (HMCA). We show that in one dimension, the prediction problem for HMCA is in NL, while in two or more dimensions, the problem is P-Complete.
Our result is based on two different techniques. For the one-dimensional case, we show that the HMCA has a property that we call
two-composition two-change. This property means that independently of how we choose the local rules and the initial configuration, a single cell can only change its state twice when we look only to the even time-steps of the dynamic. We combine this observation with a result of [
14,
15], where it is shown that the prediction problem is in
NL for a group of one-dimensional cellular automata having a property called
bounded-change. For these cellular automata, the number of times a node can change its state does not depend on the total amount of cells. Observe that this group contains a well-studied class of rules having a property called
freezing property in which the cells update its state according to a partial order defined on the alphabet [
15].
In two dimensions, we show that the combination of stable and biased majority rules allows to simulate logic gates, as well as crossing gadgets that can be used to simulate non-planar information transmission. This implies that the prediction problem in this case is P-Complete.
Context. Our results are in line with a series of articles that aim to understand the computational complexity of the majority rule by studying different variants of the problem.
The freezing majority. The freezing property means that a site in state 1 remains in that state in every future time step. Freezing automata model forest fires [
16], infection spreading [
17], bootstrap percolation [
18] and voting systems [
9]. Theoretical facts about those automata can be seen in [
14].
The prediction problem for the
freezing stable majority automata was studied by Goles et al. in [
19], where the authors showed that the in two dimensions, the prediction problem for the freezing majority automata is in
NC. At the same time, in three or more dimensions, the prediction problem is
P-Complete. Later, in [
20,
21], the authors showed an analogous result for the
freezing biased majority automata. In both articles, the efficient algorithms are based in some topological properties of the set of
stable sites, that is to say, the set of nodes initially in
that never switch their state. Unfortunately, these topological properties are not preserved when the freezing property is lifted. Hence, is unclear how to use the algorithms for freezing cases in non-freezing cases.
Majority automata networks. Another approach consists of generalizing the majority cellular automata from grids into an arbitrary graph. In that context, two perspectives have been taken in order to show the
P-completeness. In [
22], it was shown that the prediction problem for the majority rule is
P-complete, even when the topology is restricted to planar graphs where every node has an odd number of neighbors. The result is based in a crossing gadget that uses a sort of
traffic light that restricts the flow of information depending on the parity of the time-step. Then, in [
23], it is shown that the prediction problem for the majority rule is
P-complete when the topology is restricted to regular graphs of degree 3 (i.e., each node has exactly three neighbors). Both results are valid for the stable and biased majorities, as these rules are equal when the nodes have an odd number of neighbors.
Signed majority. In [
24], the authors studied the majority rule in two dimensional grids where the edges have a
sign. The
signed majority consists of a modification of the majority rule, where the most represented state in a neighborhood is computed multiplying the state of each neighbor by the corresponding sign in the edge. The authors show that when the configuration of signs is the same on every site (i.e., we have an homogeneous cellular automata) then the dynamics and complexity of the signed majority is equivalent to the standard majority. Interestingly, when the configuration of signs may differ from site to site, the prediction problem is
P-Complete.
Asynchronous prediction. A last variant considers the prediction problem under a sequential updating scheme. More precisely, the
asynchronous prediction problem asks for the existence of a permutation of the cells that produces a change in the state of a given cell in a given time-step. In fact, in [
9], Moore suggested in this case it holds a similar dichotomy than in the synchronous case: namely, the complexity in the two-dimensional case is lower than in three or more dimensions. This conjecture was proven in [
25], where it was shown that the asyncrhonous prediction in two dimension is in
NC, while it is
NP-Complete in three or more dimensions.
Organization of the Article
The article is organized as follows. In
Section 2, we begin with the main formal definitions used in the rest of the article. In
Section 3, we show that in the one-dimensional case, the heterogeneous majority rule is in
NL. Then, in
Section 4, we give the proof of the
P-completeness of the two-dimensional case. Finally, in
Section 5, we give a discussion and research perspectives.
2. Preliminaries
In this section, we give the formal definitions used along the article. We begin by defining the topologies that we consider, namely the one-dimensional, and the two-dimensional grids. We continue defining the stable majority, biased majority and heterogeneous majority cellular automata. We then formally define the Prediction problem.
Cellular Automata and Grids. Cellular automata are discrete dynamical systems defined on a regular grid of cells, where each cell changes its state by the action of a local function or automata rule, which depends on the state of the cell and the state of its neighbors. In this work, we will consider mainly two classes of grids.
First, we will consider the one-dimensional grid, where the cells are arranged in a line. The neighborhoods in this case are defined by the adjacent cells, that is to say, the left and right neighbors.
Second, we will consider the two-dimensional grid, where the cells are arranged in a rectangle of square cells, and the neighbors of each cell are simply given by the nearest cells. Thus, each cell has 4 neighbors. This definition of neighborhood is known in the literature as a Von Neumann neighborhood. This notion can be generalized to three or more dimensions in the obvious way.
In this model, each cell can only have a finite number of states. In this work, we consider only cellular automata of two states, namely and 1.
A configuration of the grid is a function x that assigns values in to a region in the d dimensional grid. For instance, if , a configuration of the two-dimensional grid is given by a square area of cells. The value of the cell u in the configuration x is denoted as .
If , we will refer as to the neighborhood of the cell u. Depending on the dimensions, a configuration x is considered to be defined over a cycle graph (one-dimensional) or a torus (two-dimensional) by identifying each cell in the boundary of x as a neighbor of the cells placed in the opposite boundary of x. In addition, for a cell , we call the restriction of x to the neighborhood of u. For a cellular automaton, the size of the neighborhood of a cell is uniform, i.e., is the same for each cell. Morever, we have that
Formally, a cellular automaton (CA) with states Q and local function is a map such that . We call F the global function or the global rule of the CA. The dynamic is defined by assigning to the configuration x a new state given by the synchronous update of the local function on x. In addition, it is also possible to define a function F by assigning to each cell a local function. In this case, it is possible to assign different rules to each cell. We will focus, during this paper, on this particular case.
Stable and Biased Majorities. In this article, we focus on the majority cellular automata. In this cellular automaton, each cell has one of two possible internal states (usually represented by ). Each cell will change its state according to a majority local rule. In each time step, this local rule forces each cell to take the most represented state in its neighborhood. Since in this work we focus only on the case in which the amount of neighbors is even (the Von Neumann neighborhood), there are some cases in which exactly one half of the neighbors are in one state and the other half are in the other. In this tie case scenario, the rule is not a priori defined. However, in the literature, different approaches are considered to define transitions in tie case scenarios.
The first case is the one known as
stable majority, in which, in the tie case scenario, the rule preserves the original state of the cell. Thus, for example, if a cell is in state 1 and there is a tie case scenario, it will remain in the state 1. Formally, the stable majority local rule is defined by:
The second case that is considered in this work is the one of the
biased majority, in which, in a tie case scenario, a cell changes to a fixed state. Formally, for
, the 1-biased majority local rule (or simply biased majority rule) is defined by:
Finally, a d-dimensional heterogeneous majority automata corresponds to a function such that for every is either the stable or the biased majority rule.
The prediction problem. In this paper, we focus on the prediction problem, which is a decision problem such that one asks if the state of a given cell will change after t-time steps for a given time. We provide hereunder a precise definition:
Bounded change cellular automata. A CA is
k-change if the number of state changes of any cell in any orbit is upper bounded by
k, formally:
A CA is bounded-change if it is
k-change for some
k. It has been proven in [
15] that for any one-dimensional bounded-change CA, the prediction problem is in the
NL class.
3. One-Dimensional Case
In this section, we show that when restricted to one-dimension, the heterogeneous majority cellular automata can be efficiently predicted. Indeed, we show that when restricted to , the problem Prediction belongs to NL. In fact, we show a stronger result: we show that if we consider the dynamics given by two consecutive iterations of an arbitrary one-dimensional HMCA, i.e., if we study the dynamics given by , where F is the global rule of the HMCA, then we have that it defines a bounded-change cellular automata.
Proposition 1 ([
15])
. Restricted to one-dimensional bounded-change cellular automata, problem Prediction is in NL.
Obviously, an HMCA is not bounded-change. For instance, if we take
,
n is even and we define the configuration
x that spatially alternates 1 and
we have that it induces a limit cycle of period two, independently of the local rule (biased or stable) that we choose. More precisely, if
and
n is even, we can define for
:
We have that for all Nevertheless, the situation is different when we look at the evolution of the rule every two time-steps. More precisely, let F be the global function of a one-dimensional HMCA, and let us call . In the following, we show that is bounded-change.
Lemma 1. Let F be a one-dimensional HMCA. Then is a two-change one-dimensional cellular automata.
Proof. For simplicity, in the following, we identify state with 0. Our proof consists of showing that, if a cell has a state transition from 0 to 1 under , then this cell will remain fixed in state 1 on every following iteration of . This means that, in total, a cell can have at most two state transitions under .
Let us denote by u an arbitrary cell such that there exists an even time-step t so that and . We claim that for every . We separate the proof of our claim in five cases, depending on the local functions of the cells adjacent to u. Let us call ℓ and r, respectively, the left and right neighbors of u.
In our figures, cell u is highlighted, and the local rules of the cells are specified by a “b” or an “s”, meaning “biased” and “stable” majorities, respectively. For instance, the case is the case where u and ℓ have the biased majority, and r has the stable majority.
In our cases, we repeatedly use the following observations. First, if in a given time-step, two adjacent cells are in state 1, then they will remain in state 1 in every future time-step independently of the local functions. Second, if, in a given time-step, two adjacent cells are in state 0, and the local function of both cells have is stable majority, then both cells will remain in state 0 in every future time-step. Now we are ready to tackle the cases.
Case 1: , and . Let us consider the case where u and ℓ have the biased majority rule (case is symmetric to ). Since u is in state 1 at time-step , then at time-step , cell ℓ will be in state 1, making u stay in state 1 in time-step . Inductively, we conclude that for every .
| ℓ | u | r |
| b | b | |
t | · | 0 | · |
| · | · | · |
| · | 1 | · |
| 1 | · | · |
| · | 1 | · |
Case 2: . This case is similar to Case 1. If cell
u reaches state 1 at time-step
, then both neighbors will be in state 1 on time-step
, which turns
u into 1 in time-step
. Inductively, we conclude that
for every
.
| ℓ | u | r |
| b | s | b |
t | · | 0 | · |
| · | · | · |
| · | 1 | · |
| 1 | · | 1 |
| · | 1 | · |
Case 3: . First notice that if
r and
ℓ are in state 0 on
t, then the three cells will remain fixed in state 0 in every future time-step, which contradicts the choice of
u and
t. Then, at least one neighbor of
u is in state 1 on
t.
Without loss of generality, let us suppose that
. This implies that
, since
u has the biased majority rule. Moreover, since
, necessarily one neighbor of
u is in state 1 at time-step
. This implies that in time-step
, cell
u and one of its neighbors are simultaneously in state 1. This implies that
for every
.
| ℓ | u | r | | s | b | s | t | 1 | 0 | · | | 1 | 1 | · | | 1 | 1 | · |
| | ℓ | u | r | | s | b | s | t | 1 | 0 | · | | · | 1 | 1 | | · | 1 | 1 |
|
Case 4: . If the three cells are ruled by the stable majority, and at least one neighbor is in state 0 at time-step
t, then
u will get fixed in 0, contradicting the choice of
u and
t. Then, we assume that
. This implies that
. Since
, then at least one of the neighbors of
u is in state 1 at time-step
(in our figure below, we assume without loss of generality that
). Then, we have two adjacent cells in state 1, making
for every
.
| ℓ | u | r |
| s | s | s |
t | 1 | 0 | 1 |
| · | 1 | 1 |
| · | 1 | 1 |
Case 5: and . Let us study the case
(the case
is symmetric). Observe that
, because otherwise we will have two adjacent stable cells in 0 in the same time-step, fixing them in every future time-step, contradicting the choice of
t and
u. Since
, at least one of the neighbors of
u has to be in 1 in time-step
.
| ℓ | u | r | | b | s | s | t | · | 0 | 1 | | · | · | 1 | | · | 1 | · |
| | ℓ | u | r | | b | s | s | t | · | 0 | 1 | | 1 | · | · | | · | 1 | · |
|
If
, then we have that
u and one of its neighbors are in state 1 in
, implying that
u and that neighbor get fixed in state 1 on every future time-step.
| ℓ | u | r | | b | s | s | t | 1 | 0 | 1 | | · | 1 | 1 | | 1 | 1 | 1 |
| | ℓ | u | r | | b | s | s | t | 1 | 0 | 1 | | 1 | 1 | · | | 1 | 1 | · |
|
If
, then necessarily
ℓ and
r are in state 1 at time-step
. Since
r has a stable-majority local rule and
, then necessarily the right neighbor of
r, namely
w, is in state 1 at time-step
t. This means that
for every
. This implies that
u and
r are in state 1 at time-step
, meaning that
for every
.
| ℓ | u | r | w |
| b | s | s | |
t | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| · | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
On all cases, we conclude that for every . Therefore, the cellular automata given by global function is 2-change. □
Theorem 1. Prediction is in NL for every one-dimensional HMCA.
Proof. Let be an input of the Prediction problem, where F is defined by some assignation of local rules . Let us denote G the global function . Observe that as a consequence of Proposition 1, there exists a nondeterministic logarithmic-space algorithm solving the Prediction problem. Suppose first that t is even. In this case, we simply run on input . Observe that . This implies that the output of on input is the answer of Prediction on input .
Suppose now that
t is odd. In this case, we run
on inputs
From the outputs given by , we can deduce the values of , and . These values correspond to the states of cells , i and in . Finally, using the local function of i, we can compute and decide the output. We deduce that Prediction is in NL. □