Introduction

Almost every practical optimizer hides the same humble idea: start somewhere, then keep making small changes that improve the score, until no small change helps anymore. That stopping point is a local optimum — a solution better than all of its neighbors. It is how we tune circuits, route trucks, place chips, and train countless heuristics.

The recipe could not be simpler to state. So here is the surprise: nobody knows an efficient algorithm that is guaranteed to reach a local optimum quickly for the hardest of these problems. The climb itself — not finding the global best, just finding any point you can't improve from — appears to be intractable.

That gap between "obviously a local optimum exists" and "we can actually get there fast" is exactly what the complexity class PLS (Polynomial Local Search) was invented to capture.

Climb the Landscape

Here is a one-dimensional landscape of bumps and valleys. Each spot has a height — the score we want to maximize. Local search lives by one rule: look at your two neighbors; if either is higher, step to the higher one; otherwise stop.

<p class="hint">A bumpy <b>landscape</b>: each bar is a spot, its height is the score. Local search only moves to a <b>higher neighbor</b>; when both neighbors are lower it <b>stops</b> — stuck at a local optimum that is rarely the tallest peak.</p>
<div id="land" class="land"></div>
<div class="status" id="status">Drop the walker, then step.</div>
<div class="btns">
  <button id="step" type="button">Step</button>
  <button id="run" type="button">Run</button>
  <button id="newland" type="button" class="ghost">New landscape</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.land { display: flex; align-items: flex-end; gap: 3px; height: 220px;
        padding: 6px; background: #f2f5f8; border: 1px solid #cdd9e3; border-radius: 8px; }
.bar { flex: 1 1 0; background: #c9ccd1; border-radius: 3px 3px 0 0; position: relative;
       transition: background .12s; cursor: pointer; min-width: 6px; }
.bar:hover { background: #b4d2ea; }
.bar.peak { background: #9fb6c8; }
.bar.walker { background: #1d3557; }
.bar.walker::after { content: "●"; position: absolute; top: -22px; left: 50%;
        transform: translateX(-50%); color: #e63946; font-size: 18px; }
.bar.done { background: #0a7d33; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Local search / hill climbing on a 1-D landscape.
// Rule: from position i, look at neighbors i-1 and i+1. If a neighbor is
// strictly higher, move to the higher one. If neither is higher, STOP — you
// are at a LOCAL OPTIMUM (height >= both neighbors). It always halts because
// every move strictly increases height and heights are bounded. The catch: the local optimum reached depends on where you start and is usually NOT the global maximum. (Johnson, Papadimitriou & Yannakakis, 1988 — PLS.)
const N = 22;
let H = [];            // heights
let pos = -1;          // walker index, -1 = not placed
let done = false;

function newLandscape(){
  H = [];
  // sum of a few sine waves -> a smooth bumpy curve with several local maxima
  const a = 1 + Math.random()*1.5, b = 2 + Math.random()*2, p1 = Math.random()*6, p2 = Math.random()*6;
  for(let i=0;i<N;i++){
    const x = i/(N-1)*Math.PI*2;
    let h = 50 + 26*Math.sin(a*x+p1) + 16*Math.sin(b*x+p2) + (Math.random()*6-3);
    H.push(Math.max(6, Math.round(h)));
  }
  pos = -1; done = false;
  render(); setStatus('Click a bar to drop the walker.','');
}

function isLocalOpt(i){
  const l = i>0 ? H[i-1] : -Infinity;
  const r = i<N-1 ? H[i+1] : -Infinity;
  return H[i] >= l && H[i] >= r;
}

function step(){
  if(pos<0){ setStatus('Click a bar to drop the walker first.',''); return false; }
  if(done) return false;
  const l = pos>0 ? H[pos-1] : -Infinity;
  const r = pos<N-1 ? H[pos+1] : -Infinity;
  let next = pos;
  if(r>H[pos] && r>=l) next = pos+1;
  else if(l>H[pos] && l>r) next = pos-1;
  if(next===pos){ // local optimum
    done = true; render();
    const best = Math.max(...H);
    const tag = H[pos]===best ? ' (this is also the global peak!)' : ' (but a taller peak exists elsewhere)';
    setStatus(fmt('Stuck at a local optimum, height %v%%tag%', { v: H[pos], tag: tag }),'ok');
    return false;
  }
  pos = next; render(); setStatus(fmt('Climbing… height %v%', { v: H[pos] }),''); return true;
}

let timer=null;
function run(){
  if(timer){ clearInterval(timer); timer=null; return; }
  if(pos<0){ setStatus('Click a bar to drop the walker first.',''); return; }
  timer = setInterval(()=>{ if(!step()){ clearInterval(timer); timer=null; } }, 280);
}

function render(){
  const c = document.getElementById('land'); c.innerHTML='';
  const max = Math.max(...H);
  for(let i=0;i<N;i++){
    const d=document.createElement('div');
    let cls='bar';
    if(i===pos) cls += done ? ' done' : ' walker';
    else if(isLocalOpt(i)) cls += ' peak';
    d.className=cls;
    d.style.height = (H[i]/max*100)+'%';
    d.title=fmt('height %v%', { v: H[i] });
    d.addEventListener('click',()=>{ if(timer){clearInterval(timer);timer=null;} pos=i; done=false; render(); setStatus(fmt('Walker dropped at height %v%. Now step.', { v: H[i] }),''); });
    c.appendChild(d);
  }
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

document.getElementById('step').addEventListener('click',step);
document.getElementById('run').addEventListener('click',run);
document.getElementById('newland').addEventListener('click',newLandscape);
newLandscape();
Result
Console

Drop the walker anywhere and press Step or Run. It only ever moves uphill, so it always halts — at a local optimum, a spot higher than both neighbors. But notice: that is rarely the tallest peak. Press New landscape and try different starting points. The same simple rule lands you on completely different summits, and there is no local move that escapes a peak once you are on it. Now imagine the landscape having millions of dimensions instead of one — and you start to feel why the climb can be brutally hard.

The Real Complexity

How hard is local search, really? Not finding the best solution — just finding any point you can't improve from.

  • A local optimum always exists. Every uphill step raises the score, the score can't rise forever, so the process must stop somewhere. The answer is guaranteed to be there — this is a total search problem (it lives in TFNP).
  • Checking is easy. Given a candidate solution, just inspect its neighbors: if none is better, it's a valid local optimum. That verification is fast.
  • PLS captures exactly this. In 1988, David Johnson, Christos Papadimitriou and Mihalis Yannakakis defined PLS — Polynomial Local Search — the class of problems where neighbors and scores are computable in polynomial time and you must output a local optimum.
  • It can be PLS-complete. Problems like finding a local optimum for Max-Cut under the flip neighborhood or weighted SAT are PLS-complete: as hard as anything in the class. The naive "keep flipping" walk can take an exponential number of steps, and no polynomial-time algorithm is known for any PLS-complete problem.

This is the punchline. Local search is the friendliest heuristic we have, yet the precise question "give me a solution nothing nearby beats" sits in its own hardness universe — related to, but distinct from, the world of P vs NP. It is widely believed that PLS-complete problems have no efficient algorithm, though, like P vs NP, this remains open.

Where It Matters

"Keep improving until you're stuck" is the beating heart of practical optimization, so PLS shows up almost everywhere:

  • Machine learning: gradient descent is local search on a loss landscape — it settles into local minima, and PLS is the theory of why escaping them has no general guarantee.
  • Game theory: in many games, players locally improving their own payoff is exactly local search, and computing the resulting Nash equilibrium can be PLS-hard.
  • Chip design and scheduling: placement, routing and timetabling are tuned by local moves; PLS explains why "just keep optimizing" sometimes never converges in reasonable time.
  • Heuristics everywhere: simulated annealing, 2-opt for routing, and hill climbing all gamble that a good enough local optimum arrives fast — PLS is the formal reason that bet can fail.

Understanding PLS reframes a daily engineering experience: when your optimizer "stalls," it may not be a bug. You may have hit the wall that the theory predicts.

Conclusion

Local search hides a quiet paradox. The answer it seeks — a point nothing nearby can beat — is guaranteed to exist and trivial to verify. Yet for the hardest cases, PLS-complete ones, we know no efficient way to actually reach it, and most researchers suspect none exists. The proof is still open.

So the next time an optimizer crawls uphill and grinds to a halt, remember what you watched in the demo: it didn't fail, it found a local optimum. The mystery is not that it stopped — it's that getting there might be, in the worst case, as hard as anything in computer science. The same flavor of difficulty echoes through P vs NP and the search for Nash equilibria.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/pls-local-search/Content licensed under CC BY-NC 4.0.