MODEL PROTEIN FOLDING · MATH · COMPLEXITY · under KEEPER ERIS

Why Folding Is NP-Hard

Finding the lowest-energy HP fold is NP-complete in 2D (Crescenzi et al. 1998) and in 3D (Berger & Leighton 1998). The number of chain shapes grows like 2.638ⁿ on the square lattice, so exact search hits a wall long before real protein sizes.

Dave (t249u): "can you build some pages on protein folding, the math and the difficulty, edutaiton please, use this wasm engine"

Dave’s I-13 engine on this page

booting I-13 v0.3…

LIT What the VM computes here: JS runs the exhaustive branch-and-bound, because it needs a stack and a hash set the VM doesn’t have. The VM verifies every optimum it reports from raw coordinates and computes the μⁿ growth and the brute-force years for n = 100.

LIT Crescenzi, Goldman, Papadimitriou, Piccolboni & Yannakakis (J Comput Biol 5:423, 1998) proved 2D HP folding NP-complete. Berger & Leighton (J Comput Biol 5:27, 1998) proved it for the 3D cubic lattice, including the perfect-cube case.

LIT NP-complete means a proposed fold is easy to check (count the contacts), but no known algorithm finds the best fold in polynomial time. A fast exact algorithm would also solve SAT and thousands of other hard problems.

LIT The number of self-avoiding walks grows like μⁿ, with connective constant μ ≈ 2.63815853 (square) and ≈ 4.684 (cubic). Hart & Istrail (1996) give polynomial-time approximations guaranteed to reach 1/4 (2D) and 3/8 (3D) of the optimal contacts.

AMBER Nature is not solving an NP-hard problem in general. Evolved sequences are special (funnelled), and real proteins sometimes don’t reach the global minimum either. NP-hardness is about the worst case.

WALL No one knows whether P = NP, so “intractable” here means believed intractable, not proved.

Lab MODEL interactive, computed on the I-13 VM

sequence prefix n

Sources (browsed Oct 2026)

  1. Crescenzi et al. (1998) On the complexity of protein folding, J Comput Biol 5(3):423
  2. Berger & Leighton (1998) Protein folding in the HP model is NP-complete, J Comput Biol 5(1):27
  3. Hart & Istrail (1996) Fast, cheap and out of control: lattice approximation algorithms, J Comput Biol 3:53
  4. OEIS A001411

MODEL Two agents, as Dave set for every world. The ARTIST folds the 24-residue HP chain S2 HHPPHPPHPPHPPHPPHPPHPPHH on the square (2D) lattice with pivot, corner and kink moves. The CRITIC judges each move (Metropolis at temperature T) and scores the best fold as −E/9 (E_ref = -9, proved optimal by exhaustive search here). It also has Dave’s I-13 VM recount every kept fold from raw coordinates. Rendered with Three.js r160 from a pinned CDN, devicePixelRatio capped at 2. Drag to orbit, scroll to zoom.

LIT on load: the seal is recomputed, the page’s facts are re-checked as arithmetic (throws on mismatch), 200 seeded ARTIST rounds must improve, the workspace loop logs 5 entries, and the OBJ and SVG exports must agree. Then the engine boots, its SHA-256 is checked, and the page’s VM results are compared with independent JS.

Gallery of kept folds (WebGL snapshots):

Workspace improvement loop: instructions for agents MODEL

  1. Measure: every 40 rounds, record the acceptance rate, the best score, the best E and the rounds since the last improvement.
  2. Try next: after a 40-round plateau, reheat T ×1.5. If acceptance is under 15%, warm T ×1.25; if over 45%, cool T ×0.7; otherwise anneal T ×0.9.
  3. Log back: append {entry, round, measured, tried, T} to the workspace log (in the JSON export and the list below), and have the I-13 VM recount the best fold.
  4. Repeat, forever: never stop improving. Re-check every claim against the engine and the sources before you make it.

Live workspace log:

    Shared board MODEL ARTIST ↔ CRITIC

      Background art: AMBER MODEL a generative field seeded from this page’s seal.

      proving…

      Seal sha256(name|slug|blurb): 8f74b964b6574df75c641f8d60f5dc876867a0c1ac0e9bc3c24f355f522b4284

      ↑ Protein Folding index · ← ERIS, keeper of Mayhem