Stable Configuration in Connectionist Model (SCCM)

Input

An undirected graph $G = (V, E)$ whose vertices and edges have integer weights coded in unary, and a configuration $C$.

Problem

Find a stable configuration of the Connectionist Model $G$.

Definitions

The vertex (edge) weights are denoted $w_i$ (respectively, $w_{ij}$). $G$ is called a Connectionist Model and has associated with it the following properties. Each vertex $v_i \in V$ has a state of either $0$ or $1$ associated with it. (Some authors consider states of $-1$ and $1$; it is known that this model is equivalent.) The state of vertex $v_i$ is denoted $s_i$. A configuration refers to the vector of vertex states, $\vec{s} = (s_1, \ldots, s_{|V|})$. The influence function for vertex $v_i$ is defined as follows: $$I_i(\vec{s}) = \sum_{v_j \in V} w_{ji}s_j + w_i.$$

The state of a vertex $v_i$ is stable in a given configuration $\vec{s}$ if and only if

1. $I_i(\vec{s}) = 0$, or
2. $I_i(\vec{s}) > 0$ and $s_i = 1$, or
3. $I_i(\vec{s}) < 0$ and $s_i = 0$.

A configuration is stable if the states of all vertices in the configuration are stable. Stable configurations coincide with local maximum with respect to the following “energy” function: $$H(\vec{s}) = \frac{1}{2} \sum_{(v_i,v_j) \in E} w_{ij}s_i s_j + \sum_{v_i \in V} w_i s_i.$$

Status

$\P$-hard (Godbeer [1], Lipscomb [2], Papadimitriou, Schäffer, and Yannakakis [3], Schäffer and Yannakakis [4]).

Remarks

The reduction to show hardness is from LFMIS. The problem is in $\mathsf{FP}$ if the weights are encoded in unary.

Many variants of this problem have been considered [1][2][4]. The complexity of the problem changes depending on the types of values (positive, negative, or both positive and negative) the weights are allowed to take on and depending on the encodings of the weights. In [1] directed and undirected versions of the problem are considered. Versions of the problem that are $\NP$-complete, $\P$-hard, and $\P$-complete are given. For example, if the problem is restricted to just positive weights, the MCVP can be reduced to it. Since this version is known to be in $\P$, it is $\P$-complete.

In [2] several variants of the general problem are presented that are $\P$-hard. In [4] they consider a slight variant of the problem and show that when it is restricted to edge weights of only $-1$, it is $\P$-complete. The version of this problem in which the weights are encoded in binary is $\mathsf{PLS}$-complete [3][4]. DasGupta describes parallel complexity results for neural networks in [5]. He shows a deterministic recurrent neural network that has at least one stable state can learn any $\P$-complete language; he gives conditions restricting the thresholds and weights that result in neural networks capable only of learning languages in $\NC$ [5].