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?