jimmy-yang.dev

Previous posts established that table edit distance is NP-hard, that treewidth controls the boundary, and that the algebraic root cause is the absence of compositional structure. Theory is clean; reality is messy. Users of tate need to diff tables today, and they need the result in milliseconds, not in the exponential time that exact computation would require.

This post covers tate’s practical answer: coordinate descent — an alternating optimization scheme that exploits the one structural property the NP-hardness result leaves intact: for any fixed column alignment, the row alignment problem is polynomial (it’s 1D LCS).

We prove convergence, characterize the optimality gap, and show how the algorithm maps to tate’s Rust implementation.

Post 1 established that table edit distance is NP-hard and that treewidth controls the boundary. Post 2 traced the boundary to its algebraic root: 1D solutions compose (lattice structure), 2D solutions don’t.

Now we ask: what about three dimensions? Four? $d$?

The answer involves a beautiful parallel. The complexity boundary $d = 1$ vs $d \geq 2$ in edit distance maps exactly onto the boundary between matrix rank (polynomial) and tensor rank (NP-hard). This is not a surface analogy — the coupling structure that makes 2D edit distance hard is the same structure that makes tensor decomposition hard.

In the first post, we established that table edit distance is NP-hard for any positive cost model, and that treewidth controls the boundary: treewidth 1 (sequences) is polynomial, unbounded treewidth (tables) is NP-hard, and bounded treewidth (few columns) is FPT.

But treewidth only tells us when the problem is tractable. It doesn’t explain why. Why does the $O(nm)$ DP fill its table correctly for sequences, but no analogous DP exists for tables? What is the structural property that makes one case solvable and the other not?

The answer comes from universal algebra: polymorphisms — operations that combine solutions into new solutions. When polymorphisms exist, the solution space has compositional structure, and dynamic programming can exploit it. When they don’t, no amount of clever algorithm design can compensate.

This is the same principle that underlies the CSP dichotomy theorem (Bulatov 2017, Zhuk 2017), one of the deepest results in theoretical computer science.

This post accompanies tate, a self-contained structured diff library in Rust. I’ll formalize table edit distance, prove it’s a metric, prove it’s NP-hard for any positive cost model (not just a specific one), and identify the treewidth boundary that separates tractable from intractable.