does local search's State-Flipping Algorithm always terminate?

Question

I am looking at the state flipping algorithm, an algorithm that tries to find a stable configuration in a Hopfield network.

The algorithm simply flips the state of unsatisfied nodes as long as the the network has not reached a stable configuration.

Please check page 673, chapter "An Application of Local Search to Hopfield Neural Networks" of the textbook Algorithm Design by Jon Kleinberg and Éva Tardos.

Figure 12.4 depicts a network ending in a stable configuration, then in the following paragraph they say about the same network. "Indeed, in the earlier directed example, this process will simply cycle through the three nodes, flipping their states sequentially forever", which implies non termination, and in the following paragraph of the same page they prove termination!

In the slides (slide 18) by the same author, they say "Hopfield network search problem: Given a weighted graph, find a stable configuration if one exists...", but there is no known poly-time algorithm for the search problem"

I am totally lost... why do we say the search problem is not polynomially solvable even though we say that the state flipping algorithm always terminates in bounded time with a stable configuration?

Answer 1

A Hopfield (neural) network is introduced as an undirected network satisfying some conditions in that book.

The book also introduces a directed Hopfield network exactly as a Hopfield network, except that "each edge is directed, and each node determines whether or not it is satisfied by looking only at edges for which it is the tail." Note that a directed Hopfield network is NOT a Hopfield network anymore.

The State-Flipping Algorithm can be applied to a Hopfield network as well as to a directed Hopfield network. That algorithm will not terminate for a certain directed Hopfield network with three nodes, although it always terminate for a Hopfield network. There is no contradiction here.

---

The State-flipping Algorithm "always terminates in bounded time with a stable configuration". However, this "bounded time" is proved to be polynomial in $n$ and $W$, not in $n$ and $\log W$. Here $n$ is the number of nodes and $W$, as a natural upper bound of $\Phi(S)$, is the total absolute weight of all edges.

For example, suppose there are $50$ nodes and the absolute maximum of the weights is $1657034118$. That textbook proves that algorithm will terminate in no more than $W$ flips, where $$W\le 50 \times 1657034118=82851705900.$$ $\log_2 82851705900\approx37$. Had the algorithm been proven to terminate in no more than something like $37^3$ flips instead, that textbook could have stated the algorithm would terminate in time polynomial in $n$ and $\log W$. The point here is the big difference between $82851705900$ and $37^3$, that becomes more significant when the maximum of weights becomes bigger.

It is not a surprise that the textbook says "it turns out to be an open question to find an algorithm that constructs stable states in time polynomial in $n$ and $\log W$ (rather than $n$ and $W$)".

More generally, there is no known algorithm for this search problem in time that is polynomial in the size of input. That is why we say "there is no known poly-time algorithm for the search problem."