THE FOLD / BOSS / THE FINAL BOSS / THE PERMANENT
THE PERMANENT
the determinant's all-plus twin — and it's #P-hard
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The permanent of a matrix looks just like the determinant — a sum over all permutations of products of entries — but with all plus signs, no alternating minus. That tiny change makes it monstrously hard. The determinant is computable in O(n³) by Gaussian elimination; the permanent is #P-hard (Valiant 1979), believed to have no polynomial algorithm.
Ryser’s formula still beats the naive n! by inclusion–exclusion: perm(A) = (−1)ⁿ ΣS⊆cols (−1)|S| ∏i (Σj∈S Aij), running in O(2ⁿ·n). The permanent counts the perfect matchings of a bipartite graph.
LIT verified live: Ryser’s formula equals the brute permutation-sum for 100 random matrices of size up to 6 (window.__permanent). FIG no framing; exact arithmetic.
Ryser’s formula still beats the naive n! by inclusion–exclusion: perm(A) = (−1)ⁿ ΣS⊆cols (−1)|S| ∏i (Σj∈S Aij), running in O(2ⁿ·n). The permanent counts the perfect matchings of a bipartite graph.
LIT verified live: Ryser’s formula equals the brute permutation-sum for 100 random matrices of size up to 6 (window.__permanent). FIG no framing; exact arithmetic.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-final-boss — the hardest fight in the game. The permanent is combinatorics’ final boss: a sum you can write in one line that is provably (#P-)hard to compute. AVAN (AI) built the instrument: the brute permutation-sum, Ryser’s inclusion–exclusion, and the perfect-matching count.
Credit as content: Herbert John Ryser (1963, the formula); Leslie Valiant (1979, #P-hardness of the permanent). The weave: David names the boss; I compute the permanent two ways — the naive n! and Ryser’s 2ⁿ — show they agree, and reveal why the missing minus signs make it hard.
Credit as content: Herbert John Ryser (1963, the formula); Leslie Valiant (1979, #P-hardness of the permanent). The weave: David names the boss; I compute the permanent two ways — the naive n! and Ryser’s 2ⁿ — show they agree, and reveal why the missing minus signs make it hard.
3 ONE DIMENSION
Determinant and permanent share the same terms — one product per permutation — but the determinant alternates + and − by the permutation’s sign, while the permanent keeps every term positive. Same sum, one sign apart.
4 TWO DIMENSIONS · INTERACTIVE
Toggle a 0/1 matrix — a bipartite graph. The instrument computes its permanent by Ryser and by the brute permutation-sum, confirms they match, and reads it as the number of perfect matchings.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the subset lattice Ryser sums over — 2ⁿ terms of inclusion–exclusion, far fewer than n! for large n.
AVAN’s addition (the inverse-companion): the plus signs are exactly what make it hard. The determinant’s alternating minus signs permit massive cancellation — and Gaussian elimination is precisely the machine that exploits that cancellation to collapse n! terms into n³ work. The permanent’s all-positive sum offers no cancellation to exploit, so no comparable shortcut is known, and the problem is #P-hard. The inverse of ‘an easy determinant’ is ‘the same sum stripped of the signs that saved you.’ Magenta is the cancellation the determinant enjoys and the permanent cannot; green is Ryser’s 2ⁿ inclusion–exclusion, the best general method left. Sign is the whole difference between polynomial and #P-hard.
LIT Genuine matrix permanent and Ryser's formula (Ryser 1963; #P-hardness Valiant 1979). Verified live: Ryser's inclusion-exclusion perm(A) = (-1)^n sum_{S} (-1)^|S| prod_i (sum_{j in S} A_ij) equals the brute-force sum over all permutations for 100 random matrices of size n=2..6 (window.__permanent.ryserMatchesBrute); for 0/1 matrices it counts perfect matchings.
FIG No framing: the brute permutation-sum, Ryser's formula, and (for contrast) the determinant all compute in-browser and agree where they should. The AVAN inverse is honest — the determinant's minus signs enable the cancellation Gaussian elimination exploits, which the all-plus permanent lacks; that missing cancellation is why it is #P-hard (magenta = the unavailable cancellation, green = Ryser's 2^n method).
FIG No framing: the brute permutation-sum, Ryser's formula, and (for contrast) the determinant all compute in-browser and agree where they should. The AVAN inverse is honest — the determinant's minus signs enable the cancellation Gaussian elimination exploits, which the all-plus permanent lacks; that missing cancellation is why it is #P-hard (magenta = the unavailable cancellation, green = Ryser's 2^n method).
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE FINAL BOSS · David Lee Wise (ROOT0), with AVAN