MINIMUM ATTRACTION RADIUS FOR BINARY HOPFIELD NET

• INSTANCE: An n-node synchronous binary Hopfield network and a stable initial vector of states $u\in\{-1,1\}^n$. A binary Hopfield network is a complete graph where each edge has an integer weight $w(v_i,v_j)$ and each vertex has an integer threshold value $t(v_i)$. At each time step t each vertex $v_{i}$ has a state $x(t,v_i)$. $x(0,v_i)$ is given by u and $x(t+1,v_i)=\mbox{\rm sgn}\left(\sum_{j=1}^n w(v_i,v_j)-t_i\right)$ where $\mbox{\rm sgn}$ is the sign function. An initial vector of states is stable if $x(t,v_i)$ eventually converges for all i.

• SOLUTION: An initial vector of states v that either converges to a different vector than u or is not stable.

• MEASURE: The Hamming distance between u and v. If v is the vector nearest to u that does not converge to the same vector as u, then this distance is the attraction radius.

  
  

• Bad News: Not approximable within $n^{1-\varepsilon }$ for any $\varepsilon >0$ [167].

• Comment: Transformation from MINIMUM INDEPENDENT DOMINATING SET.