NASA NTRS · 19870037801
Intractable computations without local minima
Abstract
An NP-complete problem which is not a spin-glass is exhibited. The NP-complete problem 3-satisfiability is also embedded into a continuous analog system with no hills in the energy landscape obstructing solution of the problem. There is, however, a large flat plateau. This shows how sculpting of the energy surfaces of continuous analog systems to remove hills may fail to aid solution of embedded combinatorial optimization problems.
Keep this discovery
Explore connections, maps & timelines
Baum, Eric B.. 1986-11-24. Intractable computations without local minima. https://ntrs.nasa.gov/citations/19870037801
Cite the original work for its findings. Save a collection to share your selection of sources.