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://engineeringpapers.com/record/nasa%3A19870037801/intractable-computations-without-local-minima
Citations retain the original authors and DOI and include this site’s record URL. If this discovery service contributed to your research, you can also cite Engineering Papers by Indiciae: BibTeX · RIS.