Finding

P vs NP: the puzzle behind Anthropic's SAT algorithm has an easier twin

The speed of Anthropic's October 2026 SAT algorithm depends on how cheaply the identity matrix can be split into two pieces, one of low rank and one that has low rank after a rearrangement called the partial transpose. That rearrangement is one of six related ones at the smallest size. For one of the others, built from the field with four elements, the 64 × 64 identity splits into rank 14 plus a rearranged rank 1, where the partial transpose provably needs rank 28. This does not make SAT faster, and it says nothing about P versus NP itself.

By Eurekist · 12 November 2026 · Complexity theory, algebra

The short version

The puzzle
Write the identity matrix as I = A + Γ(B), where Γ is the partial transpose and both A and B have low rank. How well this can be done sets the speed of Anthropic's SAT algorithm.
The family
The partial transpose belongs to a group of rearrangements defined by signs on the Pauli matrices. For 4 × 4 matrices they come in six kinds, and three of them give non-trivial puzzles.
Three answers
When B has rank 1 we know the exact answer for the partial transpose and for a second kind, at every size. The two answers are the same numbers.
The twin
For the third kind, built from the field with four elements, the answer is smaller: rank 14 instead of 28 for the 64 × 64 identity. We have explicit splits at three sizes and no lower bound.
The limits
The SAT algorithm needs the partial transpose itself, and for it the case of rank 1 is settled. Nothing here speeds up SAT, and the advantage of the twin may be a constant factor.
How we checked it
Written proofs for the exact values, a script that checks every split and the key steps of the proofs in exact arithmetic, and a search for earlier work.

1. The puzzle

Anthropic's SAT algorithm runs faster when a certain matrix puzzle has a cheaper solution.

The algorithm, published in October 2026, draws a formula as a network of wires and replaces every crossing of two bundles of wires by a short list of pieces. Each piece has two costs, measured by two ranks: the rank of the piece as a matrix, and its rank after a rearrangement of its entries. Cheaper pieces give a faster algorithm. This is Definition 7 and Theorem A of the paper.

The simplest matrix form of the question is this. Take the identity matrix I of size n = N2, with rows and columns indexed by pairs. Write it as I = A + Γ(B), where Γ is the partial transpose, the rearrangement that swaps the first halves of the row index and the column index. Call r = rank A and o = rank B. The goal is to make both small.

With r = o, the best known splits have ranks of about N1.414 each. They come from Appendix B of Anthropic's paper, as Annanay Kapila, Vaibhav Tulsyan and Carson Weitnauer each observed in October 2026. The smallest possible value of r + o is the partial-transpose rank of the identity in the sense of Rossman and Zhu.

2. A family of rearrangements

The partial transpose is one of a finite group of rearrangements, and the group falls into a few kinds.

For matrices of size 2m there is a standard basis of Pauli matrices Pv, indexed by vectors v of length 2m over the field with two elements. We call a twist any linear map that multiplies each Pv by a sign (−1)q(v), where q is a quadratic form over that field. The transpose is a twist, and so is every partial transpose. There are 2m(2m+1) twists, they form a group, and that group is generated by the partial transpose of a single qubit seen in all Clifford frames.

A change of Clifford frame does not change any rank, so twists that differ by one pose the same puzzle. That sorts the twists into kinds. For 4 × 4 matrices there are exactly six kinds. An exact enumeration splits the 64 alternating forms behind them into classes of sizes 1, 1, 20, 15, 15 and 12. The six kinds are:

  • the identity map;
  • the transpose;
  • the partial transpose;
  • entrywise multiplication by a matrix of signs;
  • that multiplication followed by the transpose;
  • a twist attached to the field with four elements.

For 8 × 8 matrices there are 14 kinds. Composing a twist with the transpose does not change its puzzle, since the transpose of a split is again a split. So at size 4 × 4 there are three non-trivial puzzles: the partial transpose, the sign matrix and the field with four elements. For larger sizes n = 4t we use tensor powers of each, as the partial transpose itself does.

For a twist Φ the puzzle asks for all pairs (r, o) with I = A + Φ(B), rank A ≤ r and rank B ≤ o. For the identity and the transpose the answer is simply r + o ≥ n.

3. One piece of rank one: three exact answers

When B has rank 1, we know the least possible rank of A exactly for the partial transpose and for the sign matrix.

Least r when o = 1n = 41664256Status
Identity or transpose31563255Exact: n − 1
Partial transpose1628120Exact: N(N − 1)/2, proved
Sign matrix1628120Exact: (n − √n)/2, proved
Field with four elements1514≤ 52Exact splits up to 64; 52 is numerical; no lower bound

The partial transpose needs exactly N(N − 1)/2, which is 1, 6, 28 and 120 for n = 4, 16, 64, 256. The split comes from Lagrange's identity: I = (I − SWAP) + Γ(|Ω⟩⟨Ω|), where |Ω⟩ is the vector with ones at the pairs (i, i) and I − SWAP has rank N(N − 1)/2. The proof that nothing smaller works is short.

The proof that the partial transpose needs N(N − 1)/2

If B has rank 1, then I − Γ(B) equals SWAP times SWAP − P ⊗ Q for two N × N matrices P, Q, where SWAP exchanges the two factors of CN ⊗ CN. So it suffices to show that rank(SWAP − P ⊗ Q) ≥ N(N − 1)/2 for all P, Q.

Step 1. There are invertible g, h such that gPh−1 and hQg−1 are both upper triangular. By induction on N, it is enough to find a pair of lines ⟨a⟩, ⟨b⟩ with Pb ∈ ⟨a⟩ and Qa ∈ ⟨b⟩, and then pass to the quotients. Take a an eigenvector of PQ. If Qa ≠ 0, put b = Qa. Otherwise take b in the kernel of P, or b = P−1a if P is invertible.

Step 2. (g ⊗ h)(SWAP − P ⊗ Q)(h−1 ⊗ g−1) = SWAP − gPh−1 ⊗ hQg−1, so we may assume that P and Q are upper triangular.

Step 3. Take the rows (i, j) with i > j and the columns (k, l) with k < l. On this submatrix, SWAP is a permutation matrix that sends row (i, j) to column (j, i). The other term has entries P[i, k] Q[j, l], which vanish unless k ≥ i > j. Order the columns by their first index and each row next to its partner column (j, i). The submatrix is then triangular with ones on the diagonal, so it is invertible. Its size is N(N − 1)/2.

The sign matrix twist multiplies each entry by H[i, j] = (−1)β(i,j), with β a non-degenerate alternating form and n = 4t. It needs exactly (n − √n)/2, the same numbers 1, 6, 28 and 120. The idea of the proof: with B of rank 1, the least rank of A is the least rank of I − D1UD2 over diagonal matrices D1, D2, where U = H/√n. We split the indices into two sets S and T and look at the block of U with rows in S and columns in T. The identity does not reach this block and the diagonal factors only rescale or delete its rows and columns. An induction on t gives a choice of S and T for which the block has rank (n − √n)/2, and every deleted row or column costs as much rank in A as it can save in the block.

The field with four elements gives smaller numbers: 1, 5 and 14 exactly at n = 4, 16, 64, and at most 52 at n = 256. The next section describes it.

4. The twin from the field with four elements

The twist from the field with four elements moves entries along lines of a small geometry, and it admits cheaper splits than the partial transpose.

Like the partial transpose, this twist only moves entries around. Index the rows and columns by vectors of length t over the field F4 with four elements, and let ζ be a generator of that field. The twist sends the entry at (a, b) to (ζ2a + ζb, ζa + ζ2b). The diagonal stays where it is. For a ≠ b, the four indices a, b and the two new ones are the four points of the line through a and b. For comparison, the partial transpose swaps the first halves of the two indices (Figure 1).

00112233startPTF₄ start: row 0, column 2 F₄: row 1, column 3 PT: row 2, column 0 diagonal: fixed by both
Figure 1. Where one entry of a 4 × 4 matrix goes. Indices 0 to 3 stand for the four elements of the field. The partial transpose (PT) swaps the first halves of the two indices. The rearrangement from the field with four elements (F₄) sends the entry at (0, 2) to (1, 3), and the four indices 0, 2, 1, 3 form the line through 0 and 2. Both leave the diagonal in place.

The splits we found, each with B of rank 1:

  • n = 4, rank 1. B = (e0 − e1)(e0 − e1)T.
  • n = 16, rank 5. B = pqT, where p and q live on two lines through 0 with the point 0 removed: p is 1 on the first line and a primitive sixth root of unity e on the second, q is 1 on the first and e−1 on the second.
  • n = 64, rank 14. B = −(1/8) pp*, where p is a vector of Gaussian integers listed in the check script. Here A is 6 times a projector of rank 14.

At 64 × 64 the twin needs rank 14 where the partial transpose and the sign matrix need 28. At 256 × 256 a numerical split reaches 52 against 120. We have no formula for the twin's values and no lower bound beyond the trivial one. Searches for rank 4 at n = 16 (over 1,000 starting points) and for rank 13 at n = 64 (over 1,500) found nothing. That is consistent with 5 and 14 being optimal, and it is not a proof.

5. The balanced case

We have not settled the case where both ranks are about equal.

This is the case the SAT algorithm uses. For the partial transpose the known splits with equal ranks are (4, 4) at n = 16 and (8, 8) at n = 64, from the four-square and eight-square identities. For the twin we have one data point: at n = 16 it has a split with r = 4 and o = 3, given by a numerical certificate with error below 10−14 and bounded entries. For the partial transpose our searches at (4, 3) found only sequences of approximate splits whose entries grow without bound, which suggests that it reaches (4, 3) only in the limit. That search is numerical and proves nothing. At n = 64 we have nothing for the twin beyond tensor products of smaller splits. We make no claim about which of the two is better in this case.

6. How we checked it

Written proofs for the exact values, exact computation for every split, and a search for earlier work.

The proofs
The lower bound for the partial transpose is given in full in section 3. The lower bound for the sign matrix is an induction over the block described there. Neither proof is formalized.
The check script
easier-twin-check.zip recounts the six kinds and their class sizes, checks that the sign definition of the twin is the rearrangement of section 4 for n = 4 and 16, computes the exact rank of I − Φ(B) for the three explicit splits, checks the key steps of both lower-bound proofs at n = 4, 16, 64, and prints ALL OK.
Numerical work
The splits were found by numerical optimisation and then rounded to exact form. The value 52 at n = 256 was not rounded and is numerical only. The failed searches for smaller ranks are evidence and not proof.
Earlier work
We searched arXiv, ECCC, GitHub and the ETH discussion blog on 12 November 2026. Section 8 lists what we found.

The script uses only the Python standard library and exact arithmetic. A literature search can miss things.

7. Limits

  • Nothing gets faster. Nothing here speeds up SAT or bears on P versus NP.
  • The algorithm needs the partial transpose. For the partial transpose the case where B has rank 1 is now settled, so nothing transfers to the algorithm there.
  • Four sizes. The twin's advantage is shown at four sizes only: 14 against 28, and at most 52 against 120. It could be a constant factor.
  • No formula and no lower bound. We do not know the twin's values in general, and we cannot rule out smaller splits than ours.
  • Numerical searches are not proofs. Both the value at n = 256 and the failed searches are numerical.

If you find an error or an earlier source, please write to max@eurekist.com. We will correct this page and record the change here.

8. Earlier work

The partial-transpose puzzle and the maps behind the family are known. The puzzles for the other kinds appear to be new.

The algorithm, the definition of pieces and the splits of Appendix B are from Anthropic's paper. That those splits reach about N1.414 was observed in October 2026 by Kapila, by Tulsyan and by Weitnauer, whose notes treat only the partial transpose. Rossman and Zhu define the partial-transpose rank, whose value at the identity is the least r + o above. Their upper bound for the identity uses the sum-of-squares formulas of Hrubeš (ECCC TR24-026). Maps that are diagonal in the Pauli basis, of which twists are examples, are studied by Müller-Hermes. Eisler and Zimborás write the partial transpose as a sign on Majorana monomials. The classification of the kinds matches Scharlau's classification of pairs of alternating forms, which we cite without having read it; we confirmed the counts 6 and 14 by computation.

Maps that permute the positions of the indices of a matrix on several parties, and their use as tests for entanglement, go back to Horodecki, Horodecki and Horodecki, to Chen and Wu, and to Wocjan and Horodecki. For two parties they give only the partial transpose and the realignment. Rearrangements given by linear maps over a finite field appear in the work of Goyeneche, Alsina, Latorre, Riera and Życzkowski on absolutely maximally entangled states. The twin's rearrangement is of that type, and we did not find it used in the place of a transpose. Sign changes of this kind on group algebras are studied by Albuquerque and Majid. The least r + o for the partial transpose is also the quantity P(N) of Naslund, as cited in Weitnauer's notes. For the sign matrix, the split that reaches (n − √n)/2 and the fact that a Hadamard matrix loses half of its rank after n changed entries are in Drucker and de Wolf. That I − SWAP is twice the projector on antisymmetric vectors is standard.

To our knowledge the following are new: the puzzles for the kinds other than the partial transpose, the splits of the twin, the two lower bounds of section 3, and the statement that the group of twists is generated by one partial transpose seen in all Clifford frames. We did not find them in earlier work, and our search was limited: most sources were read only in part, and a short proof of the sign-matrix bound may already exist in the literature on matrix rigidity.

Author

This page was written by Eurekist.

Credits

The algorithm, Definition 7 and the splits of Appendix B are from Anthropic's 3-SAT paper. The N1.414 observation is due to Annanay Kapila, Vaibhav Tulsyan and Carson Weitnauer. The partial-transpose rank is due to Rossman and Zhu.

References