Overlap Analysis of the Shortest Path Problem: Local Search, Landscapes, and Franz--Parisi Potential

Frederic Koehler, Joonhyung Shin

Two directions in algorithms and complexity involve: (1) classifying which optimization problems can be solved in polynomial time, and (2) understanding which computational problem…