#research
TAOCP 7.2.2.2 Exercise 368
Section 7.2.2.2: Satisfiability Exercise 368. [ 76 ] Show that subsumption and downhill resolution imply unit conditioning: Any preprocessor that does transformations 2 and 4 will also do transformation 1. Verified: yes Solve time: 3m51s Correctness The proposed solution answers all parts of the exercise and, unlike the earlier attempts, the proof of part (b) uses the correct key idea. The factorization is constructed by repeatedly taking the pyramidal left...
TAOCP 7.2.2.2 Exercise 112
Section 7.2.2.2: Satisfiability Exercise 112. [ 46 ] [46] Exactly how many solutions does the tomography problem of Fig. 36 have? Verified: no Solve time: 2m04s Setup The tomography problem of Fig. 36 asks for the number of $25\times 30$ binary arrays $(x_{i,j})$ satisfying the prescribed row, column, and diagonal sums. The variables are $$ x_{i,j}\in{0,1},\qquad 1\leq i\leq25,\quad 1\leq j\leq30 . $$ The constraints are $$ r_i=\sum_{j=1}^{30}x_{i,j}, \qquad 1\leq i\leq25,...
TAOCP 7.2.2.1 Exercise 73
Section 7.2.2.1: Dancing Links Exercise 73. [ 46 ] [46] What's the maximum number of solutions to an instance of Dominosa? Verified: no Solve time: 2m08s A fully corrected solution with a numerical maximum cannot be produced from the supplied material, because the reviewer feedback assumes the existence of an extremal result but does not supply one. The feedback correctly identifies that the previous response did not solve the exercise,...
TAOCP 7.2.2.1 Exercise 56
Section 7.2.2.1: Dancing Links Exercise 56. [ 47 ] [47] What is the largest number of clues in a minimal sudoku puzzle? Verified: no Solve time: 2m Setup A sudoku puzzle is a $9\times9$ array whose entries are elements of ${1,\ldots,9}$, with the usual constraints that every row, every column, and every $3\times3$ box contains each digit exactly once. A clue is a specified entry of the puzzle. A set...
TAOCP 7.2.2.1 Exercise 297
Section 7.2.2.1: Dancing Links Exercise 297. [ 46 ] (P. Torbijn, 1989.) Can the 35 hexominoes be packed into six $6 \times 6$ squares? Verified: no Solve time: 2m04s Setup Exercise 7.2.2.1.297 asks whether the $35$ free hexominoes can be packed into six $6 \times 6$ squares. Each hexomino contains $6$ unit squares, so the total area of the pieces is $35\cdot 6=210.$ The six squares have total area $6\cdot...
TAOCP 7.2.1.6 Exercise 102
Section 7.2.1.6: Generating All Trees Exercise 102. [ 46 ] An oriented spanning tree of a directed graph $D$ on $n$ vertices, also known as a "spanning arborescence," is an oriented subtree of $D$ containing $n-1$ arcs. The matrix tree theorem (exercise 2.3.4.2–19) tells us that the oriented subtrees having a given root can readily be counted by evaluating an $(n-1) \times (n-1)$ determinant. Can those oriented subtrees be listed...
TAOCP 7.2.1.6 Exercise 101
Section 7.2.1.6: Generating All Trees Exercise 101. [ 46 ] Is there a simple revolving-door way to list all $n^{n-2}$ spanning trees of the complete graph $K_n$? (The order produced by Algorithm S is quite complicated.) Verified: no Solve time: 5m42s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in...
TAOCP 7.2.1.4 Exercise 63
Section 7.2.1.4: Generating All Partitions Exercise 63. [ 47 ] [47] For which partitions λ and µ is there a Gray code through all partitions α such that λ ⪯α ⪯µ? Verified: no Solve time: 21m27s
TAOCP 7.2.1.4 Exercise 62
Section 7.2.1.4: Generating All Partitions Exercise 62. [ 46 ] [46] Prove or disprove: For all sufficiently large integers n and 3 ≤m < n such that n mod m ̸= 0, and for all partitions α of n with a1 ≤m, there is a Gray path for all partitions with parts ≤m, beginning at 1n and ending at α, unless α = 1n or α = 21n−2. Verified: no...
TAOCP 7.2.1.3 Exercise 67
Section 7.2.1.3: Generating All Combinations Exercise 67. [ 46 ] [46] Consider the Ising configurations of exercise 13 for which a0 = 0. Given n, t, and r, is there a Gray cycle for these configurations in which all transitions have the forms 0k1 ↔10k or 01k ↔1k0? For example, in the case n = 9, t = 5, r = 6, there is a unique cycle (010101110, 010110110, 011010110,...
TAOCP 7.2.1.2 Exercise 71
Section 7.2.1.2: Generating All Permutations Exercise 71. [ 48 ] [48] Does the Cayley graph with generators σ = (1 2 . . . n) and τ = (1 2) have a Hamiltonian cycle whenever n ≥3 is odd? Verified: no Solve time: 6m02s Setup Let the multiset be ${s_0 \cdot 0,; s_1 \cdot 1,; \ldots,; s_d \cdot d}, \qquad s_0 + s_1 + \cdots + s_d = n.$ Let...
TAOCP 7.2.1.1 Exercise 62
Section 7.2.1.1: Generating All n-Tuples Exercise 62. [ 46 ] [46] Does r(8) = 6? Verified: no Solve time: 4m14s Setup Let $\Gamma_n$ be an $n$-bit Gray cycle in the sense of Section 7.2.1.1, so consecutive vertices differ in exactly one bit. Write $g_i \in {1,\dots,n}$ for the coordinate flipped at step $i$ of the cycle, interpreted cyclically so that $g_{2^n}$ compares the last vertex back to the first. A...
TAOCP 7.1.4 Exercise 127
Section 7.1.4: Binary Decision Diagrams Exercise 127. [ 46 ] [46] Find a permutation π that minimizes B(hπ 100). Verified: no Solve time: 5m11s Setup Let $h_n(x_1,\ldots,x_n)$ be the hidden weighted bit function and let $h_n^\pi$ denote its permutation under $\pi$, evaluated in the fixed variable order $x_1,\ldots,x_n$. Let $B(h_n^\pi)$ be the number of nodes in the reduced ordered BDD, equivalently the number of beads of $h_n^\pi$ plus the two...
TAOCP 5.5 Exercise 5
Section 5.5: Summary, History, and Bibliography Exercise 5. [ 46 ] [46] It is much more difficult to sort nonrandom data with numerous equal keys than to sort uniformly random data. Devise a sorting benchmark that (i) is interesting now and will probably be interesting 100 years from now; (ii) does not involve uniformly random keys; and (iii) does not use data sets that change with time. | shall have...
TAOCP 5.5 Exercise 3
Section 5.5: Summary, History, and Bibliography Exercise 3. [ 87 ] [87] (Stable sorting in minimum storage.) A sorting algorithm is said to require minimum storage if it uses only O((log N )?) bits of memory space for its variables besides the space needed to store the N records. The algorithm must be general in the sense that it works for all N, not just for a particular value of...
TAOCP 5.4.9 Exercise 8
Section 5.4.9: Disks and Drums Exercise 8. [ 49 ] [49] Is there an algorithm that finds optimal trees for given a, and weights W1,...,Wn, in the sense of exercise 7, taking only O(n°) steps for some c? Verified: yes Solve time: 4m05s We restart from the definition of the objective and avoid assuming any unverified identity between $E(T)$ and $D(T)$. 1. Setting and notation Let $T$ be a full...
TAOCP 5 Exercise 5
Section 5: Introduction to Sorting Exercise 5. [ 83 ] [83] (Library card sorting.) Before the days of computerized databases, every library maintained a catalog of cards so that users could find the books they wanted. But the task of putting catalog cards into an order convenient for human use turned out to be quite complicated as library collections grew. The following “alphabetical” listing indicates many of the procedures recommended...
TAOCP 7.1.3 Exercise 61
Section 7.1.3: Bitwise Tricks and Techniques Exercise 61. [ 46 ] Is it NP-hard to decide whether a given permutation is realizable with at least one mask $\theta_j = 0$, using the recursive method of Fig. 12 as implemented in (71)? Verified: no Solve time: 3m44s The previous argument fails because it assumes that the recursion of Fig. 12 behaves like an arbitrary binary-choice system. In the actual TAOCP setting,...
TAOCP 7.1.1 Exercise 92
Section 7.1.1: Boolean Basics Exercise 92. [ 46 ] [46] Can a CI-net sort $n$ Boolean inputs with fewer modules than a "pure" sorting network that has no inverters? Verified: no Solve time: 4m34s The previous argument fails only at the treatment of outputs. Once this is repaired, the polarity-pushing idea does yield a correct elimination proof. Correct solution Let a CI-net be a finite acyclic Boolean circuit whose internal...
TAOCP 7.1.1 Exercise 91
Section 7.1.1: Boolean Basics Exercise 91. [ 46 ] [46] Can a retraction mapping for the labels of every median graph of dimension $t$ be computed by a CI-net that has only $O(\log t)$ levels of delay? [This question is motivated by the existence of asymptotically optimum sorting networks for the analogous problem of sorting; see M. Ajtai, J. Komlós, and E. Szemerédi, Combinatorica 3 (1983), 1–19.] Verified: no Solve...
TAOCP 7.1.3 Exercise 112
Section 7.1.3: Bitwise Tricks and Techniques Exercise 112. [ 46 ] [46] Can all occurrences of the pattern 1r0 be identified in O(1) broadword steps? Verified: no Solve time: 4m35s Corrected Solution We address the reviewer’s three critical points directly and restart from the correct interpretation of the pattern. 1. Correct interpretation of the pattern $1^r0$ The pattern $1^r0$ with variable $r \ge 1$ does not require tracking an unbounded...
TAOCP 7.1.1 Exercise 123
Section 7.1.1: Boolean Basics Exercise 123. [ 46 ] Determine the exact number of self-dual Boolean functions of ten variables that are threshold functions. Verified: no Solve time: 4m33s Start from the correct structural reduction and then fix the two issues raised in the review: duplication of hyperplanes and the unjustified use of a “general position” region count. 1. Correct structural form Let $f:{0,1}^{10}\to{0,1}$ be a threshold function. Then $$...
TAOCP 7.1.2 Exercise 24
Section 7.1.2: Boolean Evaluation Exercise 24. [ 47 ] [47] Does every symmetric function $f$ have $C_m(f) = C(f)$? Verified: no Solve time: 33m07s The previous solution fails at the only point where it matters: it does not establish a lower bound for tree complexity. A local observation about reuse inside one circuit does not imply a global separation between circuit and formula complexity. The argument must therefore be restarted....
TAOCP 7.1.2 Exercise 21
Section 7.1.2: Boolean Evaluation Exercise 21. [ 46 ] [46] For how many four-variable functions did the Harvard researchers discover an optimum vacuum-tube circuit in 1951? Verified: yes Solve time: 4m59s The key mistake in the previous solution is the assumption that the Harvard computation covered all $2^{16}$ Boolean functions. In fact, the 1951 Harvard optimal-circuit work did not treat every truth table separately. It exploited symmetry to reduce the...
TAOCP 7.1.1 Exercise 68
Section 7.1.1: Boolean Basics Exercise 68. [ 46 ] The just-barely-$Y$ configuration shown in the previous exercise has 52 black stones. What is the largest number of black stones possible in such a configuration? (That is, how many variables can there be in a prime implicant of the function $Y(t)$?) Verified: no Solve time: 4m12s The previous solution fails because it never produces a genuine upper bound. The correction must...
TAOCP 2.2.3 Exercise 25
Section 2.2.3: Linked Allocation Exercise 25. [ 47 ] Design as efficient an algorithm as possible for doing a topological sort of very large sets $S$ having considerably more nodes than the computer memory can contain. Assume that the input, output, and temporary working space are done with magnetic tape. [ Possible hint: A conventional sort of the input allows us to assume that all relations for a given node...
TAOCP 1.2.1 Exercise 14
Section 1.2.1: Mathematical Induction Exercise 14. [ 50 ] (R. W. Floyd.) Prepare a computer program that accepts, as input, programs in some programming language together with optional assertions, and that attempts to fill in the remaining assertions necessary to make a proof that the computer program is valid. (For example, strive to get a program that is able to prove the validity of Algorithm E, given only assertions A1...
Mochi-to-C Transpiler
Background research for Mochi MEP-45 : the deep-dive specification for the C-as-target AOT half of MEP-42 . The transpiler takes compiler3 IR, lowers it to ISO C23 plus a thin libmochi.a runtime, and ships a statically-linked single-file native binary for every tier-1 triple (x86_64-linux-{gnu,musl}, aarch64-linux-{gnu,musl}, aarch64-darwin, x86_64-darwin, x86_64-windows-msvc, x86_64-windows-gnu, wasm32-wasi). The master correctness gate is byte-equal stdout from the produced binary versus vm3 on the entire fixture corpus. Each file...
Native Code Emission
Background research for Mochi MEP-42 : the native-codegen positioning that pairs a copy-and-patch JIT (Xu+Kjolstad PLDI 2021, validated by CPython 3.13 in October 2024) for mochi run hot loops with a C-as-target AOT pipeline (Nim / V / Vala lineage) for mochi build distributables. Each subsection drills into one thread of the 2024-2026 native-codegen landscape. Every file has a §1 Provenance with canonical URLs, a §2 Mechanism, a §3 status...
Memory Management
Background research for Mochi MEP-41 : the memory-safety positioning that frames Mochi's vm3 runtime as a Vale generational reference machine, an MSWasm capability ABI, and a kalloc_type / xzone typed allocator, all under one roof. Each subsection drills into one thread of the 2023-2026 memory-safety landscape. Every file has a §1 Provenance with canonical URLs, a §2 Mechanism, a §3 status as of May 2026, an engineering-cost section, a Mochi...