The Longest Increasing Subsequence Problem revisited
This paper reveals that the Longest Increasing Subsequence problem, despite being solvable in polynomial time, exhibits glassy dynamics and thermodynamic sparsity at low temperatures, where local search algorithms become trapped in metastable states due to a lack of accessible configurations rather than energetic barriers.