Introduction
Let w 1 , … , w N w_1,\ldots,w_N w 1 , … , w N N ≥ 2 N \ge2 N ≥ 2 binary prefix code is a tuple C = ( C 1 , … , C N ) \mathcal{C}=(C_1,\ldots,C_N) C = ( C 1 , … , C N ) { 0 , 1 } \{0,1\} { 0 , 1 } C i C_i C i C j C_j C j C i C_i C i i i i ∣ C i ∣ 0 |C_i|_0 ∣ C i ∣ 0 ∣ C i ∣ 1 |C_i|_1 ∣ C i ∣ 1 ∣ C i ∣ = ∣ C i ∣ 0 + ∣ C i ∣ 1 |C_i|=|C_i|_0+|C_i|_1 ∣ C i ∣ = ∣ C i ∣ 0 + ∣ C i ∣ 1 { 0 , 10 , 11 } \{0,10,11\} { 0 , 10 , 11 } { 0 , 01 , 11 } \{0,01,11\} { 0 , 01 , 11 }
In the classical binary prefix coding problem , the objective is to minimize the weighted length
L ( C ) = ∑ i = 1 N w i ∣ C i ∣ . L(\mathcal{C})=\sum_{i=1}^{N}w_i|C_i|. L ( C ) = i = 1 ∑ N w i ∣ C i ∣. Dividing by W = ∑ i w i W=\sum_i w_i W = ∑ i w i w i / W w_i/W w i / W [19 ] solved this fundamental problem in lossless source coding in 1952 by a greedy algorithm. With a priority queue, the algorithm uses O ( N log N ) O(N\log N) O ( N log N ) equal-letter-cost setting : if both encoding letters have a common positive cost c c c c L ( C ) cL(\mathcal{C}) c L ( C )
In the unequal-letter-cost setting , the encoding letters have costs 0 < c 0 < c 1 0<c_0<c_1 0 < c 0 < c 1
cost c 0 , c 1 ( C ) = ∑ i = 1 N w i ( c 0 ∣ C i ∣ 0 + c 1 ∣ C i ∣ 1 ) . \operatorname{cost}_{c_0,c_1}(\mathcal{C})=\sum_{i=1}^{N}w_i(c_0|C_i|_0+c_1|C_i|_1). cost c 0 , c 1 ( C ) = i = 1 ∑ N w i ( c 0 ∣ C i ∣ 0 + c 1 ∣ C i ∣ 1 ) . Thus composition matters as well as length: with costs ( 1 , 3 ) (1,3) ( 1 , 3 ) [1 Section 2.7] and discussed in [14 , 16 ] .
Binary Prefix Coding with Unequal Letter Costs. The input consists of positive integer frequencies w 1 , … , w N w_1,\ldots,w_N w 1 , … , w N N ≥ 2 N \ge2 N ≥ 2 c 0 < c 1 c_0<c_1 c 0 < c 1 K K K C \mathcal{C} C
cost c 0 , c 1 ( C ) ≤ K . \operatorname{cost}_{c_0,c_1}(\mathcal{C})\le K. cost c 0 , c 1 ( C ) ≤ K . The corresponding optimization problem omits K K K
Unequal-letter-cost coding has a long history, and Karp gave an integer-programming formulation in 1961 [21 ] . Nevertheless, when the letter costs are part of the input, the exact computational complexity had remained unresolved: even proving NP-hardness was a longstanding open problem. This question was explicitly highlighted in the approximation work of Golin, Mathieu, and Young [14 ] , in its full version [16 ] , and subsequently in [6 Section 4] .
Our contribution
We resolve this longstanding open problem by proving NP-completeness for a binary encoding alphabet, even when the two letter costs differ by only one.
Theorem 1.1. Deciding whether there is a binary prefix code of cost at most K K K ( c 0 , c 1 ) = ( M , M + 1 ) (c_0,c_1)=(M,M+1) ( c 0 , c 1 ) = ( M , M + 1 ) M M M
Consequently, finding an exact minimum-cost code is NP-hard. Here M M M [17 , 4 ] . Our reduction uses frequencies and letter costs that may have exponential magnitude but have polynomial binary encoding length. It establishes ordinary NP-hardness. Strong NP-hardness and the existence of a fully polynomial-time approximation scheme (FPTAS) remain open.
Secondary optimization among minimum-length codes. The construction also identifies a source of difficulty within ordinary prefix coding. Minimizing expected length can leave several optimal codes, and a secondary criterion can distinguish them. Such questions have a classical precedent: Schwartz [29 ] studied minimum-redundancy codes with minimum maximum codeword length and minimum total codeword length, and Kou [22 ] gave an algorithm for minimizing codeword-length variance among minimum-redundancy codes. We consider a different secondary criterion, depending on the actual encoding letters rather than just the codeword lengths.
For a code C C C
R ( C ) = ∑ i = 1 N w i ∣ C i ∣ 1 . R(C)=\sum_{i=1}^{N}w_i|C_i|_1. R ( C ) = i = 1 ∑ N w i ∣ C i ∣ 1 . Let
L ∗ ( w ) = min C L ( C ) , R ∗ ( w ) = min C : L ( C ) = L ∗ ( w ) R ( C ) . L^*(\mathbf{w})=\min_C L(C), \qquad R^*(\mathbf{w})=\min_{C:L(C)=L^*(\mathbf{w})}R(C). L ∗ ( w ) = C min L ( C ) , R ∗ ( w ) = C : L ( C ) = L ∗ ( w ) min R ( C ) . Huffman's algorithm computes L ∗ ( w ) L^*(\mathbf{w}) L ∗ ( w ) secondary optimization problem asks for a code attaining R ∗ ( w ) R^*(\mathbf{w}) R ∗ ( w ) w = ( w 1 , … , w N ) \mathbf{w}=(w_1,\ldots,w_N) w = ( w 1 , … , w N ) κ ≥ 0 \kappa\geq0 κ ≥ 0 R ∗ ( w ) ≤ κ R^*(\mathbf{w})\leq\kappa R ∗ ( w ) ≤ κ
cost c 0 , c 1 ( C ) = c 0 L ( C ) + ( c 1 − c 0 ) R ( C ) . \operatorname{cost}_{c_0,c_1}(C)=c_0L(C)+(c_1-c_0)R(C). cost c 0 , c 1 ( C ) = c 0 L ( C ) + ( c 1 − c 0 ) R ( C ) . For costs ( M , M + 1 ) (M,M+1) ( M , M + 1 ) M L + R ML+R M L + R M M M M M M Theorem 1.1 ; the quantitative argument is given in § 4.3 .
Corollary 1.2. Given positive integer frequencies w 1 , … , w N w_1,\ldots,w_N w 1 , … , w N N ≥ 2 N\geq2 N ≥ 2 κ \kappa κ κ \kappa κ
§ 2.4 presents the key ideas behind the reductions. The full proof of the corollary is given in § 4.4 .
The corollary ranges over all minimum-length prefix codes, including different tree shapes, symbol assignments, and choices of which branches receive zero and one. In particular, minimizing the ( 1 , 2 ) (1,2) ( 1 , 2 ) L + R L+R L + R L = L ∗ ( w ) L=L^*(\mathbf{w}) L = L ∗ ( w ) O ( N 2 ) O(N^2) O ( N 2 ) unrestricted optimization with the fixed costs ( 1 , 2 ) (1,2) ( 1 , 2 ) [4 ] : that algorithm may trade a larger weighted length for a smaller weighted number of ones.
Prior work
Origins and motivation. Huffman’s minimum-redundancy construction [19 ] is the starting point for this line of research. Unequal-letter-cost coding has a long history, including Karp’s integer-programming formulation [21 ] ; Abrahams [1 Section 2.7] surveys the problem and its connections with source coding and search trees. In addition to differing transmission times, unequal costs arise in storage models. For example, the coding literature relates run-length restrictions used in magnetic and optical storage to unequal costs by regarding strings 0 j 1 0^{j}1 0 j 1 j + 1 j+1 j + 1 [14 , 16 ] . These applications motivate optimizing letter costs rather than codeword lengths alone.
Exact algorithms. The known exact running times depend strongly on the letter costs. For positive integer costs with maximum value c c c [17 ] gave an O ( N c + 2 ) O(N^{c+2}) O ( N c + 2 ) [4 ] improved the binary case to O ( N c ) O(N^{c}) O ( N c ) [11 ] obtained the same bound for every fixed number of encoding letters. Consequently, every fixed pair of positive integer letter costs admits an exact polynomial-time algorithm. These bounds do not give a polynomial-time algorithm when the costs themselves are supplied in binary as part of the input.
Approximation and the exact-complexity question. Early bounds and constructions were obtained by Krause [25 ] , Mehlhorn [27 ] , and Altenkamp and Mehlhorn [2 ] . Golin and Li [15 ] subsequently improved several algorithms and guarantees. Golin, Mathieu, and Young [14 ] gave a polynomial-time approximation scheme (PTAS), allowing input-dependent letter costs. They also emphasized the missing hardness result: “nor is the problem known to be NP-hard.” For each fixed ε > 0 \varepsilon> 0 ε > 0 ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) [16 ] achieves running time O ( N ) + O ε ( log 3 N ) O(N)+O_{\varepsilon}(\log^{3}N) O ( N ) + O ε ( log 3 N ) ε \varepsilon ε 1 / ε 1/\varepsilon 1/ ε [6 Section 4] . Theorem 1.1 answers the NP-completeness question but not the separate FPTAS question.
Special cases and related objectives. The equiprobable case has a separate line of exact algorithms [31 , 9 , 28 , 23 , 18 ] , closely connected to optimal lopsided trees , whose branches have unequal costs [7 ] . Golin and Young [18 ] gave an O ( N log 2 r ) O(N\log^{2}r) O ( N log 2 r ) r r r alphabetic coding , where source symbols must occur in a prescribed left-to-right order at the leaves, Itai [20 ] gave a polynomial-time algorithm permitting unequal letter costs. Neither equiprobable frequencies nor an alphabetic restriction is assumed here. Fujiwara and Jacobs [12 Theorem 3] prove NP-hardness for objectives over full binary trees with arbitrary nonnegative, symbol-dependent functions of ordinary depth, allowing nonmonotone costs. The full-tree restriction is essential to their hardness proof, as explained in [6 Appendix A.1] . Such functions can specify separate depth preferences for individual symbols. Our result uses ordinary frequencies and one common pair of positive letter costs ( M , M + 1 ) (M,M+1) ( M , M + 1 )
The intermediate problem and proof overview
Our source problem is Planar Independent Set. A graph is simple if it has no loops or multiple edges, and planar if it admits a drawing in the plane with no crossing edges. An independent set of a graph G = ( V , E ) G=(V,E) G = ( V , E ) S ⊆ V S\subseteq V S ⊆ V S S S
Planar Independent Set (source problem). The input is a simple planar graph G = ( V , E ) G=(V,E) G = ( V , E ) k k k G G G k k k
This problem is NP-complete: a set is independent if and only if its complement is a vertex cover, and planar Vertex Cover is NP-complete [13 ] . For the corresponding optimization problem, the input is G G G α ( G ) \alpha(G) α ( G )
Our final target problem is Binary Prefix Coding with Unequal Letter Costs , defined in § 1 , restricted to the letter costs ( M , M + 1 ) (M,M+1) ( M , M + 1 ) M M M K K K
The reduction has two stages. The first reduction maps the source problem to an auxiliary tree-scoring problem, which we call Minimum-Score Tree with Prescribed Leaf Profile and abbreviate as the leaf-profile problem . The second reduction maps the leaf-profile problem to the final coding problem. Figure 1 shows these two stages. § 3 gives the first reduction and its forward and reverse arguments; Appendices § 8 and B supply the local proofs, realization details, and score estimates. § 4 gives the second reduction and its full proof.
Figure 1. The two-stage reduction. The middle instance consists of a leaf profile and signed coefficient rows, not a tree. Both instance transformations are polynomial-time reductions.
Trees, depths, and coordinate profiles
A rooted ordered binary tree is a finite rooted tree with at most one left child and at most one right child at each vertex. A vertex with no children is a leaf ; any other vertex is an internal vertex . The tree is full if every internal vertex has both children. Label left edges by zero and right edges by one. The root-to-leaf words then form a binary prefix code, and assigning source symbols to the leaves specifies their codewords. Conversely, a binary prefix code has such a tree representation, possibly with one-child vertices. With positive frequencies and letter costs, suppressing a vertex with only one child preserves the prefix property and strictly decreases both weighted length and coding cost. Repeating this operation produces a full code tree. Hence every optimal code is full, and every nonfull competitor can be improved to a full one.
The depth of a vertex is the number of edges on its path from the root; the root has depth zero. Its coordinate is the number of right edges on that path. Thus the path 010 has depth three and coordinate one. A vertex at depth d d d z z z d + 1 d+1 d + 1 z z z z + 1 z+1 z + 1 height of a tree is its largest vertex depth. A leaf at depth d d d z z z
M ( d − z ) + ( M + 1 ) z = M d + z M(d-z)+(M+1)z=Md+z M ( d − z ) + ( M + 1 ) z = M d + z when the letter costs are ( M , M + 1 ) (M,M+1) ( M , M + 1 )
A coordinate profile records these coordinates level by level, with multiplicities. Let X t X_t X t t t t X X X E ( X ) \mathcal{E}(X) E ( X ) z z z z + 1 z+1 z + 1 z ∈ X z\in X z ∈ X H H H
X 0 = { 0 } , X t ⊆ E ( X t − 1 ) ( 1 ≤ t ≤ H ) , X H = ∅ . X_0=\{0\},\qquad X_t\subseteq\mathcal{E}(X_{t-1})\quad(1\le t\le H),\qquad X_H=\varnothing. X 0 = { 0 } , X t ⊆ E ( X t − 1 ) ( 1 ≤ t ≤ H ) , X H = ∅ . where inclusion is multiset inclusion. The leaf-coordinate multiset at depth t t t
L t = E ( X t − 1 ) − X t . L_t=\mathcal{E}(X_{t-1})-X_t. L t = E ( X t − 1 ) − X t . For example, E ( { 0 , 1 } ) = { 0 , 1 , 1 , 2 } \mathcal{E}(\{0,1\})=\{0,1,1,2\} E ({ 0 , 1 }) = { 0 , 1 , 1 , 2 }
Conversely, every such sequence is realized by a full ordered binary tree: at each level, retain child occurrences with the coordinates prescribed by X t X_t X t
The leaf-profile problem
The leaf profile of a tree of height H H H ( n 1 , … , n H ) (n_1,\ldots,n_H) ( n 1 , … , n H ) n t n_t n t t t t feasible if at least one full ordered binary tree has exactly those leaf counts and no other leaves. We consider only feasible profiles.
Minimum-Score Tree with Prescribed Leaf Profile.
Input. A feasible leaf profile ( n 1 , … , n H ) (n_1,\ldots,n_H) ( n 1 , … , n H ) n H > 0 n_H>0 n H > 0 N = ∑ t = 1 H n t ≥ 2 N=\sum_{t=1}^{H}n_t\ge2 N = ∑ t = 1 H n t ≥ 2 t t t
u t , 1 ≥ u t , 2 ≥ ⋯ ≥ u t , n t . u_{t,1}\ge u_{t,2}\ge\cdots\ge u_{t,n_t}. u t , 1 ≥ u t , 2 ≥ ⋯ ≥ u t , n t . There is one explicitly listed coefficient for each depth-position pair
( t , k ) ∈ P : = { ( t , k ) : 1 ≤ t ≤ H , 1 ≤ k ≤ n t } . (t,k)\in\mathcal{P}:=\{(t,k):1\le t\le H,\ 1\le k\le n_t\}. ( t , k ) ∈ P := {( t , k ) : 1 ≤ t ≤ H , 1 ≤ k ≤ n t } . All integers are encoded in binary. The coefficients may be negative; a depth with n t = 0 n_t=0 n t = 0
Feasible solution. A full ordered binary tree T T T n t n_t n t t t t
Objective. At each depth t t t T T T
z t , 1 ( T ) ≤ ⋯ ≤ z t , n t ( T ) . z_{t,1}(T)\le\cdots\le z_{t,n_t}(T). z t , 1 ( T ) ≤ ⋯ ≤ z t , n t ( T ) . Minimize
score ( T ) = ∑ t = 1 H ∑ k = 1 n t u t , k z t , k ( T ) . (1) \operatorname{score}(T)=\sum_{t=1}^{H}\sum_{k=1}^{n_t}u_{t,k}z_{t,k}(T). \tag*{(1)} score ( T ) = t = 1 ∑ H k = 1 ∑ n t u t , k z t , k ( T ) . (1) The index k k k OPT t r e e ( I ) \operatorname{OPT}_{\mathrm{tree}}(\mathcal{I}) OPT tree ( I ) I \mathcal{I} I
Decision version. In addition to I \mathcal{I} I τ \tau τ T T T score ( T ) ≤ τ \operatorname{score}(T) \le\tau score ( T ) ≤ τ
Checking feasibility of the profile. Put
I 0 = 1 , I t = 2 I t − 1 − n t ( 1 ≤ t ≤ H ) . I_0 = 1,\qquad I_t = 2I_{t-1} - n_t\qquad(1 \le t \le H). I 0 = 1 , I t = 2 I t − 1 − n t ( 1 ≤ t ≤ H ) . The profile is feasible if and only if every I t ≥ 0 I_t \ge0 I t ≥ 0 I H = 0 I_H = 0 I H = 0 I t I_t I t t t t n t n_t n t 2 I t − 1 2I_{t-1} 2 I t − 1 I t I_t I t I H = 0 I_H = 0 I H = 0 n t = 2 I t − 1 − I t n_t = 2I_{t-1} - I_t n t = 2 I t − 1 − I t
A full tree with N N N N − 1 N - 1 N − 1 I I I 2 I = I + N − 1 2I = I + N - 1 2 I = I + N − 1 H ≤ N − 1 H \le N - 1 H ≤ N − 1 ( n 1 , n 2 ) = ( 1 , 2 ) (n_1,n_2) = (1,2) ( n 1 , n 2 ) = ( 1 , 2 )
Example: one instance and the score of a feasible tree. Consider the full tree whose root-to-leaf words are
00 , 11 , 010 , 011 , 100 , 101. 00,\quad11,\quad010,\quad011,\quad100,\quad101. 00 , 11 , 010 , 011 , 100 , 101. The tree and its coordinate profile are displayed below. Filled vertices are internal; the number inside each vertex is its coordinate. The words below leaves identify their paths, not additional input labels.
Figure 1 (PDF p. 9).
Table 1.
Its leaf profile is ( n 1 , n 2 , n 3 ) = ( 0 , 2 , 4 ) (n_1,n_2,n_3) = (0,2,4) ( n 1 , n 2 , n 3 ) = ( 0 , 2 , 4 ) N = 6 N = 6 N = 6 ( I 0 , I 1 , I 2 , I 3 ) = ( 1 , 2 , 2 , 0 ) (I_0,I_1,I_2,I_3) = (1,2,2,0) ( I 0 , I 1 , I 2 , I 3 ) = ( 1 , 2 , 2 , 0 ) X 2 X_2 X 2 ( 1 , 1 , 2 , 2 ) (1,1,2,2) ( 1 , 1 , 2 , 2 )
For a concrete scoring instance, choose the nonincreasing coefficient rows
( u 2 , 1 , u 2 , 2 ) = ( 2 , − 1 ) , ( u 3 , 1 , u 3 , 2 , u 3 , 3 , u 3 , 4 ) = ( 3 , 1 , − 2 , − 4 ) . (u_{2,1},u_{2,2}) = (2,-1),\qquad(u_{3,1},u_{3,2},u_{3,3},u_{3,4}) = (3,1,-2,-4). ( u 2 , 1 , u 2 , 2 ) = ( 2 , − 1 ) , ( u 3 , 1 , u 3 , 2 , u 3 , 3 , u 3 , 4 ) = ( 3 , 1 , − 2 , − 4 ) . There are no coefficients at depth one. On the displayed tree,
score ( T ) = ( 2 ⋅ 0 − 1 ⋅ 2 ) + ( 3 ⋅ 1 + 1 ⋅ 1 − 2 ⋅ 2 − 4 ⋅ 2 ) = − 2 − 8 = − 10. \begin{aligned}
\operatorname{score}(T) &= (2\cdot0 - 1\cdot2) + (3\cdot1 + 1\cdot1 - 2\cdot2 - 4\cdot2) \\
&= -2 - 8 = -10.
\end{aligned} score ( T ) = ( 2 ⋅ 0 − 1 ⋅ 2 ) + ( 3 ⋅ 1 + 1 ⋅ 1 − 2 ⋅ 2 − 4 ⋅ 2 ) = − 2 − 8 = − 10. The instance consists of the profile and these six coefficients.
Why the coefficient rows are nonincreasing. For a fixed tree and depth, pairing the largest coefficient with the smallest coordinate minimizes the sum over all assignments of those coefficients to the leaves. Indeed, if u > v u > v u > v p > q p > q p > q
( u p + v q ) − ( u q + v p ) = ( u − v ) ( p − q ) > 0. (up+vq) - (uq+vp) = (u-v)(p-q) > 0. ( u p + v q ) − ( u q + v p ) = ( u − v ) ( p − q ) > 0. Repeatedly removing such inversions gives precisely the sorted pairing in (1) , including when coefficients are negative or coordinates are repeated. This observation will allow unrestricted symbol assignments in the second reduction.
The first reduction uses auxiliary coordinate intervals and graph instructions to construct the profile and coefficients. Neither the intervals nor the instructions are additional constraints in the leaf-profile instance. A feasible tree need only have the prescribed leaf counts; its score is evaluated using the final coefficient rows. Individual contributions used to construct a row need not be nonincreasing, but the final row must be. The second reduction receives only this feasible leaf profile and these final coefficient lists.
The intended solution correspondences
The first reduction constructs from G G G I G \mathcal{I}_G I G C C C S S S T S T_S T S
score ( T S ) = C − ∣ S ∣ . \operatorname{score}(T_S) = C - |S|. score ( T S ) = C − ∣ S ∣. Constructing I G \mathcal{I}_G I G S S S T ∅ T_{\varnothing} T ∅ C C C C C C C − score ( T ) C-\operatorname{score}(T) C − score ( T )
OPT t r e e ( I G ) = C − α ( G ) , \operatorname{OPT}_{\mathrm{tree}}(\mathcal{I}_G) = C - \alpha(G), OPT tree ( I G ) = C − α ( G ) , and the decision threshold becomes τ = C − k \tau= C-k τ = C − k § 3 constructs the instance, and § 3.2 and § 3.3 prove these correspondences, with supporting details in Appendices § 8 and B.
The second reduction maps any leaf-profile instance I \mathcal{I} I J \mathcal{J} J ( M , M + 1 ) (M,M+1) ( M , M + 1 ) T T T C T C_T C T
cost ( C T ) = β + score ( T ) , \operatorname{cost}(C_T) = \beta+\operatorname{score}(T), cost ( C T ) = β + score ( T ) , where β \beta β I \mathcal{I} I T T T
OPT c o d e ( J ) = β + OPT t r e e ( I ) . \operatorname{OPT}_{\mathrm{code}}(\mathcal{J}) = \beta+\operatorname{OPT}_{\mathrm{tree}}(\mathcal{I}). OPT code ( J ) = β + OPT tree ( I ) . § 4 constructs the coding instance and proves these statements, including the polynomial-time instance and solution mappings. Neither stage requires an optimal solution in order to construct its output instance.
Key ideas
We use an intermediate leaf-profile problem tailored to the transition from Planar Independent Set to prefix coding with unequal letter costs. Related questions concerning prescribed leaf profiles and codeword compositions have been studied before [BGN26, KZ11]. To the best of our knowledge, the precise optimization problem used here, which combines a prescribed leaf profile with a signed linear score on sorted right-edge counts, has not been studied previously.
The central idea of the first reduction is to represent the execution of an independent-set verifier by the growth of a binary tree. From a planar drawing of the graph, we generate a fixed program using a small set of instructions designed for this purpose. Its input is a bit assignment to the vertices, with bit one indicating a selected vertex. The instructions store each vertex choice, copy it for the incident edge tests, and check that no edge has both endpoints selected. The planar sweep orders these operations so that every edge test uses adjacent stored values. To introduce a new vertex choice, the program first splits off a fresh known value from a reserve at the left end of the stored sequence. The PASS instruction carries it across intervening bit values; only after it reaches the required position does CHOOSE assign the new vertex bit. Planarity makes the incoming edges consecutive, so this procedure needs to exchange only a known value with a bit. A complete intended execution exists exactly when the input assignment represents an independent set. Such an execution outputs a feasible solution, namely a tree, for the leaf-profile instance constructed from the graph (§ 3.2 ).
An execution grows this tree from the root downwards, one instruction block at a time. At each instruction boundary, the continuing internal vertices store the current values: a known value has a fixed coordinate ρ \rho ρ ρ + b \rho+ b ρ + b b ∈ { 0 , 1 } b \in\{0,1\} b ∈ { 0 , 1 } ρ \rho ρ
We next translate this program into intermediate code , borrowing terminology from compiler design. This is a numerical working table with one row for each depth of the eventual tree. For every sorted leaf position at that depth, it specifies an allowed coordinate interval and temporary coefficients. The intervals and coefficients are fixed during code generation, while the intended leaf coordinates can still depend on the input bits. The placement rules separate each local operation from the waiting values, keeping their descendant coordinates in a fixed order as the bits vary. This lets us attach the local leaf data to the globally sorted ranks in the score (Lemma 3.1 ). The final coefficient at each position is computed from the temporary coefficients and interval endpoints in the completed table (§ 3.1.3 and § 3.1.5 ). Thus the graph alone determines a single leaf-profile instance; each independent-set assignment determines a tree for that same instance.
The key difficulty is to make the leaf-profile objective enforce this behavior for competing trees. Intervals of width one allow either bit value, but need not by themselves force the intended transition. Signed coefficients cancel the bit-dependent terms in an intended transition; with correct inputs, any complete block with the prescribed leaf counts and intervals but an unintended sequence of internal coordinate multisets costs at least one more. The final coefficients give interval compliance the highest priority, then instruction correctness in execution order, and finally the reward for selecting vertices. Earlier instructions receive larger multipliers, so the penalty at the first incorrect block exceeds every possible saving in later blocks and all vertex-choice rewards, even if the later inputs have been corrupted. Thus every profile-feasible tree of score at most a computable baseline C C C ( T S ) = C − ∣ S ∣ (T_S) = C - |S| ( T S ) = C − ∣ S ∣ S S S § 3.2 –§ 3.3 and Lemma 3.2 ). This is the contribution of the program representation: prescribed leaf counts and a linear score suffice to make a low-scoring tree carry out the independent-set computation.
The second reduction turns the tree score into a coding cost. We create one symbol for each prescribed leaf position. Its frequency has a large positive part that makes the required depths cheapest, plus a smaller adjustment given by the score coefficient. We choose consecutive letter costs ( M , M + 1 ) (M, M+1) ( M , M + 1 ) M M M § 4 ).
Two identities explain why these score constructions work. First, for an integer coordinate z z z [ ℓ , r ] [\ell,r] [ ℓ , r ] ( z − ℓ ) ( z − r ) (z-\ell)(z-r) ( z − ℓ ) ( z − r )
∑ t , k 2 H − t ( z t , k 2 + ( H − t ) z t , k ) . \sum_{t,k} 2^{H-t}\left(z_{t,k}^{2}+(H-t)z_{t,k}\right). t , k ∑ 2 H − t ( z t , k 2 + ( H − t ) z t , k ) . Expanding one vertex into its two children changes this expression by an amount depending only on its depth, and the profile fixes how many vertices are expanded at each depth. Consequently, after expanding the penalties and weighting those at depth t t t 2 H − t 2^{H-t} 2 H − t Lemma A.1 ). This is how a linear score enforces narrow intervals in the interior of the coordinate range.
Second, the large frequency part of a symbol assigned depth d d d Γ 2 H − d \Gamma2^{H-d} Γ 2 H − d Γ \Gamma Γ t t t Γ 2 H − t − 1 \Gamma2^{H-t-1} Γ 2 H − t − 1 Lemma 4.1 ). The same large frequency terms can thus force symbol depths while leaving the tree score as the remaining objective.
The first reduction: from the source problem to the leaf-profile problem
Let G = ( V , E ) G=(V,E) G = ( V , E ) n = ∣ V ∣ n=|V| n = ∣ V ∣ m = ∣ E ∣ m=|E| m = ∣ E ∣ § 3.1 : the graph program, numerical instruction tables, placement and assembly rules, final coefficients, and decision threshold. § 3.2 explains how an independent set determines a feasible tree, and § 3.3 recovers an independent set from any tree of sufficiently low score. § 3.4 combines these directions; Appendix B supplies the supporting details.
Construction: from graph to leaf profile
The construction first fixes a planar drawing and uses it to generate a graph program : a finite list of instructions acting on an ordered sequence of records. Subsequent steps will assign numerical coordinates to these records, expand the instructions into local tree constructions, and form the leaf counts and coefficient rows of I G I_G I G
A planar drawing and the sweep order
Fix a crossing-free straight-line drawing of G G G y y y ( x , y ) ↦ ( x , y + s x ) (x,y)\mapsto(x,y+sx) ( x , y ) ↦ ( x , y + s x ) s s s 0 , 1 , … , n 2 0,1,\ldots,n^2 0 , 1 , … , n 2
Process the vertices in increasing order of their drawing heights. Equivalently, move a horizontal sweep line upwards, processing one vertex whenever the line reaches it. At a vertex v v v u v uv uv incoming if y ( u ) < y ( v ) y(u) < y(v) y ( u ) < y ( v ) outgoing if y ( u ) > y ( v ) y(u) > y(v) y ( u ) > y ( v ) A u v A_{uv} A uv
An edge is active after its lower endpoint has been processed and before its upper endpoint has been processed. Between vertex heights, every active edge intersects the sweep line once. Order the active edges from left to right by their intersection points. This order cannot change between successive vertices: an exchange in order would require two edges to cross.
Immediately below a vertex v v v v v v v v v v v v v v v
We use the left-to-right order immediately below v v v v v v check the incoming edges in the reverse order, from right to left , and then leave records for the outgoing edges in their left-to-right order. The reason for this check order will be explicit in the program construction below. This consecutive-group property is the role of planarity: it lets us arrange all edge checks using neighboring records, without exchanging two independently chosen bits.
Running example. For the running examples throughout this section, use G = K 4 − b d G = K_4 - bd G = K 4 − b d
V = { a , b , c , d } , E = { a b , a c , a d , b c , c d } , V = \{a,b,c,d\}, \qquad E = \{ab,ac,ad,bc,cd\}, V = { a , b , c , d } , E = { ab , a c , a d , b c , c d } , and the crossing-free drawing
a = ( 0 , 0 ) , b = ( − 2 , 1 ) , c = ( 0 , 3 ) , d = ( 2 , 4 ) . a = (0,0), \qquad b = (-2,1), \qquad c = (0,3), \qquad d = (2,4). a = ( 0 , 0 ) , b = ( − 2 , 1 ) , c = ( 0 , 3 ) , d = ( 2 , 4 ) . The vertex order is a , b , c , d a,b,c,d a , b , c , d Figure 2 shows the drawing and the sweep. The relevant edge orders are summarized in Table 1. For example, at c c c ( b c , a c ) (bc,ac) ( b c , a c ) a c , b c ac,bc a c , b c d d d ( c d , a d ) (cd,ad) ( c d , a d ) a d , c d ad,cd a d , c d
Figure 2. The running example K 4 − b d K_4-bd K 4 − b d
Table 1 (PDF p. 14). The incoming and outgoing orders at each vertex of the running example. Active edges not incident with the current vertex keep their relative order.
Converting the graph into a program
We describe the ordered local operations by a program with the following instructions:
Split, Choose, Copy, Pass, Check, End, Wait, Move.
We describe their effects on records below; the local tree constructions, leaf tables, and coefficients implementing these effects will be given later. Reading the fixed drawing in the order above generates a program using these instructions. Generating the program is distinct from executing it with a bit assignment.
This recalls Cook’s computation-history encoding: a witness is checked through a sequence of locally constrained transitions [8 ] . Here the witness bits record vertex choices, and tree geometry and scores enforce the transitions.
Records and their types. A record is a bookkeeping entry in an ordered list. It tracks a continuing position in the tree construction, together with the role for which that position is being kept. In an intended tree realization, the records at an instruction boundary will represent the internal vertices awaiting further expansion at a common depth. They are not graph vertices or leaves of the output tree.
There are two types of record. A known record will represent a vertex whose coordinate is fixed by the construction, independently of all graph choices. A bit record is labeled by a graph vertex u u u b u ∈ { 0 , 1 } b_u \in\{0,1\} b u ∈ { 0 , 1 } Known ( r ) \operatorname{Known}(r) Known ( r ) Var ( u , r ) \operatorname{Var}(u,r) Var ( u , r ) r r r r + b u r+b_u r + b u r r r
The initial sequence is [ Z ] [Z] [ Z ] Z Z Z reserve record corresponding to the eventual tree root at coordinate zero. The reserve keeps the name Z Z Z v v v A v A_v A v A v K A_v^{K} A v K A v A_v A v u u u u v uv uv A u v A_{uv} A uv A u v A_{uv} A uv b u b_u b u b v b_v b v b u b_u b u
At the end of processing each graph vertex, the sequence consists of Z Z Z symbolic state of the program construction.
Creating a choice and its copies. The instruction Split ( Z ) \operatorname{Split}(Z) Split ( Z ) Z Z Z A v K A_v^{K} A v K
[ Z , … ] ⟼ [ Z , A v K , … ] . [Z,\ldots] \longmapsto[Z,A_v^{\mathrm{K}},\ldots]. [ Z , … ] ⟼ [ Z , A v K , … ] . Every record therefore originates from the initial reserve, through successive splits and copies. The numerical implementation of a split is fixed; no graph bit is chosen by it.
After the fresh known record has reached its required position, Choose( v ) (v) ( v ) v v v program generation , this writes the variable b v b_v b v ( A v ) (A_v) ( A v ) b v b_v b v A v , A v A_v,A_v A v , A v A v w 1 , … , A v w d A_{vw_1},\ldots,A_{vw_d} A v w 1 , … , A v w d
Changing order versus changing coordinates. A fresh known record can be moved through the sequence by repeated Pass operations. Each Pass selects that known record and the bit record immediately to its right, and replaces the pair by the same bit record followed by a known record:
[ … , A v K , A u w , … ] ⟼ [ … , A u w , A v K , … ] . [\ldots,A_v^{\mathrm{K}},A_{uw},\ldots]\longmapsto[\ldots,A_{uw},A_v^{\mathrm{K}},\ldots]. [ … , A v K , A u w , … ] ⟼ [ … , A u w , A v K , … ] . The bit b u b_u b u b u b_u b u A v K A_v^{\mathrm{K}} A v K
Move has a different purpose: it increases a selected record’s numerical base by one, preserving its type and stored bit. In the scheduled placements, it does not exchange neighboring records or insert a record at a different index. The later coordinate-placement stage inserts these moves. The accompanying Wait operations preserve non-selected records while the selected operation runs, keeping all continuing records at a common tree depth. Neither operation changes the abstract list of record roles. Thus Pass, not Move, is used here to change a fresh record’s position in the symbolic sequence.
Testing an edge and removing records. The instruction Check( u v ) (uv) ( uv ) b u b_u b u u v uv uv b v b_v b v
The instruction End likewise has no continuing output, but removes just one record, known or variable, whose role is finished. Consequently, a selected instruction uses one record or an adjacent pair and has zero, one, or two continuing outputs. The outputs replace the selected input segment, without reordering the other records. In the eventual tree, “removing a record” will mean terminating its continuing descendants as leaves; it will not mean deleting already constructed vertices. The record sequence grows under Split and Copy, and shrinks under Check and End.
Generating the instructions for a vertex. Suppose the sweep reaches v v v u 1 v , … , u p v u_1v,\ldots,u_pv u 1 v , … , u p v v w 1 , … , v w d vw_1,\ldots,vw_d v w 1 , … , v w d
First apply Split( Z ) (Z) ( Z ) Z Z Z A v K A_v^{\mathrm{K}} A v K every record preceding the destination, not only records of edges incident with v v v v v v Z Z Z Choose ( v ) \operatorname{Choose}(v) Choose ( v )
Now check the incoming edges from right to left. Before each check, copy the current A v A_v A v Check \operatorname{Check} Check
[ A u 1 v , … , A u p v , A v ] → Copy [ A u 1 v , … , A u p v , A v , A v ] → Check ( u p v ) [ A u 1 v , … , A u p − 1 v , A v ] . [A_{u_1v},\ldots,A_{u_pv},A_v]
\xrightarrow{\operatorname{Copy}}
[A_{u_1v},\ldots,A_{u_pv},A_v,A_v]
\xrightarrow{\operatorname{Check}(u_pv)}
[A_{u_1v},\ldots,A_{u_{p-1}v},A_v]. [ A u 1 v , … , A u p v , A v ] Copy [ A u 1 v , … , A u p v , A v , A v ] Check ( u p v ) [ A u 1 v , … , A u p − 1 v , A v ] . Any records before or after this displayed segment are unchanged. This shows why the right-to-left order is used: the surviving copy of A v A_v A v p p p A v A_v A v p = 0 p=0 p = 0
If d > 0 d>0 d > 0 Copy \operatorname{Copy} Copy d − 1 d-1 d − 1 d d d A v w 1 , … , A v w d A_{vw_1},\ldots,A_{vw_d} A v w 1 , … , A v w d d = 0 d=0 d = 0 End ( A v ) \operatorname{End}(A_v) End ( A v ) v v v End ( Z ) \operatorname{End}(Z) End ( Z )
Running example: the generated program. For the drawing of K 4 − b d K_4-bd K 4 − b d § 3.1.1 , the sequence starts as [ Z ] [Z] [ Z ] Table 2 gives the symbolic state after every instruction, using the notation just defined.
Table 2 : The 27 graph-level instructions for K 4 − b d K_4 - bd K 4 − b d K K K Z Z Z A A A
Table 2. The 27 graph-level instructions for K 4 − b d K_4 - bd K 4 − b d K K K Z Z Z A A A
At a. There are no incoming edges. Split Z Z Z b a b_a b a
[ Z , A a b , A a c , A a d ] . [Z,A_{ab},A_{ac},A_{ad}]. [ Z , A ab , A a c , A a d ] . At b. The only incoming edge is a b ab ab A b K A_b^{K} A b K A a b A_{ab} A ab A a c A_{ac} A a c A a d A_{ad} A a d Choose ( b ) \operatorname{Choose}(b) Choose ( b ) A b A_b A b a b ab ab A a b A_{ab} A ab A b c A_{bc} A b c
[ Z , A b c , A a c , A a d ] . [Z,A_{bc},A_{ac},A_{ad}]. [ Z , A b c , A a c , A a d ] . At c. Its incoming group is ( b c , a c ) (bc,ac) ( b c , a c ) A b c A_{bc} A b c A a c A_{ac} A a c A a d A_{ad} A a d Choose ( c ) \operatorname{Choose}(c) Choose ( c ) a c ac a c b c bc b c A c A_c A c A c d A_{cd} A c d
[ Z , A c d , A a d ] . [Z,A_{cd},A_{ad}]. [ Z , A c d , A a d ] . At d. Its incoming group is ( c d , a d ) (cd,ad) ( c d , a d ) Choose ( d ) \operatorname{Choose}(d) Choose ( d ) a d ad a d c d cd c d [ Z , A d ] [Z,A_d] [ Z , A d ] d d d A d A_d A d [ Z ] [Z] [ Z ] [ ] [] [ ]
The program has 27 graph-level instructions: four splits, four choices, seven copies, five passes, five checks, and two terminations. The five edge checks occur in the order a b ab ab a c ac a c b c bc b c a d ad a d c d cd c d b d bd b d
The input to the program is supplied later. A bit assignment is a function b : V → { 0 , 1 } b: V \to\{0,1\} b : V → { 0 , 1 } S b = { v ∈ V : b v = 1 } S_b = \{v \in V : b_v = 1\} S b = { v ∈ V : b v = 1 } S b = { b , d } S_b = \{b,d\} S b = { b , d } ( b a , b b , b c , b d ) = ( 0 , 1 , 0 , 1 ) (b_a,b_b,b_c,b_d) = (0,1,0,1) ( b a , b b , b c , b d ) = ( 0 , 1 , 0 , 1 )
We have therefore obtained from the drawing a program with specified record types, selected inputs, and ordered outputs at every step. The next steps assign bases and replace these symbolic instructions by numerical leaf data. § 3.2 proves that an independent set supplies an execution realizing those fixed data.
Instruction blocks and templates
The graph program specifies the order of operations and the records selected by each operation. We now describe how it is expanded into a numerical working table , with one row for every depth of the eventual tree. In this intermediate code generation step, each instruction is replaced by a local tree construction, together with waiting for the other records. We first specify these templates; § 3.1.4 then assigns their bases, inserts coordinate-placement moves, and assembles the depth rows. The working table retains interval endpoints and temporary coefficients; a subsequent step will combine them into the final coefficient rows of the leaf-profile instance.
Inputs, outputs, and numerical bases. A record has a type, a role in the program, and a numerical base. To distinguish a base from the right endpoint r t , k r_{t,k} r t , k ρ \rho ρ ( ρ ) (\rho) ( ρ ) ρ \rho ρ ( v , ρ ) (v,\rho) ( v , ρ ) ρ + b v \rho+ b_v ρ + b v b v b_v b v ( v ) (v) ( v )
Each instruction has a fixed rule for updating the bases and types of its continuing outputs. For example,
Var ( v , ρ ) → COPY [ Var ( v , ρ + 1 ) , Var ( v , ρ + 5 ) ] . \operatorname{Var}(v,\rho) \xrightarrow{\operatorname{COPY}} [\operatorname{Var}(v,\rho+1),\operatorname{Var}(v,\rho+5)]. Var ( v , ρ ) COPY [ Var ( v , ρ + 1 ) , Var ( v , ρ + 5 )] . Both output bases are computable without evaluating b v b_v b v § 3.1.4 computes all required bases and inserts one-unit MOVE instructions; it uses the upper value ρ + 1 \rho+1 ρ + 1 ρ \rho ρ ( 0 ) (0) ( 0 )
Instruction blocks and the current tree depth. In an intended realization, the current records at an instruction boundary represent vertices at one common depth h h h d d d h + d h+d h + d
The selected construction, together with waiting by all other current records, is its instruction block . As summarized in Table 4 , Move, Choose, Check, and End have three levels; Pass has five; and Copy and Split have six. Here Split is the copying construction applied to a known input viewed as bit zero. Number the expanded blocks 1 , … , J 1,\ldots,J 1 , … , J d i d_i d i i i i
Table 4. Selected-operation counts and intended enforcing scores. Outside waits are added separately.
h 0 = 0 , h i = h i − 1 + d i , H = h J . h_0=0,\qquad h_i=h_{i-1}+d_i,\qquad H=h_J. h 0 = 0 , h i = h i − 1 + d i , H = h J . Block i i i h i − 1 + 1 , … , h i h_{i-1}+1,\ldots,h_i h i − 1 + 1 , … , h i j j j t = h i − 1 + j t=h_{i-1}+j t = h i − 1 + j i ( t ) i(t) i ( t ) h i ( t ) − 1 < t ≤ h i ( t ) h_{i(t)-1}<t\le h_{i(t)} h i ( t ) − 1 < t ≤ h i ( t )
The data in a row. After all contributions at depth t t t n t n_t n t ( t , 1 ) , … , ( t , n t ) (t,1),\ldots,(t,n_t) ( t , 1 ) , … , ( t , n t ) ( t , k ) (t,k) ( t , k )
( ℓ t , k , r t , k , e t , k , δ t , k ) . (\ell_{t,k},r_{t,k},e_{t,k},\delta_{t,k}). ( ℓ t , k , r t , k , e t , k , δ t , k ) . The endpoints specify an interval [ ℓ t , k , r t , k ] [\ell_{t,k},r_{t,k}] [ ℓ t , k , r t , k ] r t , k − ℓ t , k ∈ { 0 , 1 } r_{t,k}-\ell_{t,k}\in\{0,1\} r t , k − ℓ t , k ∈ { 0 , 1 } e t , k e_{t,k} e t , k temporary enforcing coefficient supplied by the instruction or an outside wait. The marker δ t , k \delta_{t,k} δ t , k ( v ) (v) ( v ) u t , k u_{t,k} u t , k
The endpoints refer to a leaf coordinate , not to the base of a continuing record. In an intended execution, substituting the bits determines the actual leaf coordinates jointly through the tree construction. A variable wait, for example, emits ρ + 1 + b v \rho+1+b_v ρ + 1 + b v [ ρ + 1 , ρ + 2 ] [\rho+1,\rho+2] [ ρ + 1 , ρ + 2 ] ρ + 1 − b v \rho+1-b_v ρ + 1 − b v [ ρ , ρ + 1 ] [\rho,\rho+1] [ ρ , ρ + 1 ]
As in § 2 , k k k t t t
Why the other records must wait. Expanding just the selected inputs would leave all other records at the old depth. To keep a common current depth, every unselected starting record follows a d d d x x x x x x x + 1 x+1 x + 1 Figure 3 ). After d d d h + d h+d h + d x x x
Figure 3. Three levels of intended waiting, beginning at depth h h h x = ρ x=\rho x = ρ x = ρ + b v x=\rho+b_v x = ρ + b v
The waiting entries are numerical before execution. For Known( ρ ) (\rho) ( ρ ) ( [ ρ + 1 , ρ + 1 ] , 0 , 0 ) ([\rho+1,\rho+1],0,0) ([ ρ + 1 , ρ + 1 ] , 0 , 0 ) ( v , ρ ) (v,\rho) ( v , ρ ) [ ρ + 1 , ρ + 2 ] [\rho+1,\rho+2] [ ρ + 1 , ρ + 2 ] d − 1 d-1 d − 1 − 1 -1 − 1
( d − 1 ) ( ρ + 1 + b v ) − ( d − 1 ) ( ρ + 1 + b v ) = 0 , (d-1)(\rho+1+b_v)-(d-1)(\rho+1+b_v)=0, ( d − 1 ) ( ρ + 1 + b v ) − ( d − 1 ) ( ρ + 1 + b v ) = 0 , and for a known record all coefficients are zero. Lemma A.5 proves the score gap to any unintended wait. Only unselected starting records receive these outside waits. Temporary internal vertices of the selected construction follow its own template, as do preliminary left-child steps inside Move, Choose, and End.
One template in detail: Copy. At a prescribed base ρ \rho ρ ( v , ρ ) (v,\rho) ( v , ρ ) b v b_v b v
To see the corresponding intended tree growth, temporarily give the input bit a value b b b ρ + b + i \rho+b+i ρ + b + i 0 ≤ i ≤ 5 0\le i\le5 0 ≤ i ≤ 5 ρ + b \rho+b ρ + b ρ + 6 + b \rho+6+b ρ + 6 + b ρ + 1 + b \rho+1+b ρ + 1 + b ρ + 5 + b \rho+5+b ρ + 5 + b
( ρ + b ) − ( ρ + 6 + b ) = − 6 , (\rho+b)-(\rho+6+b)=-6, ( ρ + b ) − ( ρ + 6 + b ) = − 6 , independently of the bit; this is the temporary enforcing score, not the final contribution after the priority multipliers are applied. The selected internal counts are ( 2 , 4 , 8 , 16 , 2 , 2 ) (2,4,8,16,2,2) ( 2 , 4 , 8 , 16 , 2 , 2 )
caption: The selected Copy template. Its leaf counts are ( 0 , 0 , 0 , 0 , 30 , 2 ) (0, 0, 0, 0, 30, 2) ( 0 , 0 , 0 , 0 , 30 , 2 ) h h h j j j h + j h + j h + j
instruction uses the same six rows, including the width-one intervals, with a known input viewed as bit zero. It produces [Known(ρ + 1 \rho+ 1 ρ + 1 ρ + 5 \rho+ 5 ρ + 5 − 6 -6 − 6 Lemma A.2 .
The remaining instruction templates. We now give the fixed tables for the other selected instructions. Together with the Wait and Copy/Split data above, they specify every entry needed by the block-assembly rule. As before, local level j j j h h h h + j h + j h + j ( I , e , δ ) (I, e, \delta) ( I , e , δ ) { a } \{a\} { a } [ a , a ] [a, a] [ a , a ]
Table 4 collects the selected leaf counts and intended enforcing scores. If an instruction selects p p p α j \alpha_j α j
γ 0 = p , γ j = 2 γ j − 1 − α j . \gamma_0 = p,\qquad\gamma_j = 2\gamma_{j-1} - \alpha_j. γ 0 = p , γ j = 2 γ j − 1 − α j . Thus the tables also determine the complete depth profile after outside waits are added. For example, Check has continuing counts ( 2 , 2 , 0 ) (2, 2, 0) ( 2 , 2 , 0 ) ( 2 , 2 , 2 , 2 , 2 ) (2, 2, 2, 2, 2) ( 2 , 2 , 2 , 2 , 2 ) § 8 .
The table records only enforcing scores; an original Choose also contributes the separate choice term specified below. A variable record always uses the variable template, including when its eventual bit is zero. Its type is not changed to Known by substituting a bit value.
Move. A three-level Move raises the base by one, preserving the record’s type and any stored bit:
Known ( ρ ) ⟶ Known ( ρ + 1 ) , Var ( v , ρ ) ⟶ Var ( v , ρ + 1 ) . \operatorname{Known}(\rho) \longrightarrow\operatorname{Known}(\rho+1), \qquad\operatorname{Var}(v,\rho) \longrightarrow\operatorname{Var}(v,\rho+1). Known ( ρ ) ⟶ Known ( ρ + 1 ) , Var ( v , ρ ) ⟶ Var ( v , ρ + 1 ) . Its intended execution retains the left child twice and then the right child. Each level emits one selected leaf and retains one selected nonleaf. The complete fixed entries are
Table 3.
All reward markers are zero. Lemma A.5 and Appendix § 8 .6 prove the stated behavior and enforcing scores.
Choose. For an original graph vertex v v v
Known ( ρ ) ⟶ Var ( v , ρ ) . \operatorname{Known}(\rho) \longrightarrow\operatorname{Var}(v,\rho). Known ( ρ ) ⟶ Var ( v , ρ ) . Each level emits one selected leaf and retains one selected nonleaf. The first two levels retain the left child at the known coordinate ρ \rho ρ b v = 0 b_v=0 b v = 0 b v = 1 b_v=1 b v = 1
Table 9.
The enforcing score is zero for both choices. The marked leaf has coordinate ρ + 1 − b v \rho+1-b_v ρ + 1 − b v v v v v v v § 8 .6.
Check. The three-level interface selects adjacent records
[ Var ( u , ρ − 3 ) , Var ( v , ρ ) ] ⟶ [ ] . [\operatorname{Var}(u,\rho-3),\operatorname{Var}(v,\rho)] \longrightarrow[]. [ Var ( u , ρ − 3 ) , Var ( v , ρ )] ⟶ [ ] . All enforcing coefficients and reward markers are zero. The complete fixed table is
Table 10.
Lemma A.3 shows that this block has a unique complete sequence of coordinate multisets satisfying the intervals, of score zero, for each input other than ( b u , b v ) = ( 1 , 1 ) (b_u,b_v)=(1,1) ( b u , b v ) = ( 1 , 1 )
Pass. The five-level interface exchanges a known position with an adjacent variable record:
[ Known ( ρ − 1 ) , Var ( v , ρ ) ] ⟶ [ Var ( v , ρ ) , Known ( ρ + 4 ) ] . [\operatorname{Known}(\rho-1),\operatorname{Var}(v,\rho)] \longrightarrow[\operatorname{Var}(v,\rho),\operatorname{Known}(\rho+4)]. [ Known ( ρ − 1 ) , Var ( v , ρ )] ⟶ [ Var ( v , ρ ) , Known ( ρ + 4 )] . Every level emits two selected leaves and retains two selected nonleaves. All reward markers are zero. The complete fixed table is
Table 11.
The variable retains its bit and base. Lemma A.4 proves that the intended sequence of coordinate multisets has score zero and uniquely minimizes the score among all complete interval-respecting sequences, with no restriction on their final internal coordinates.
End. A three-level End has no continuing output:
Known ( ρ ) ⟶ [ ] , Var ( v , ρ ) ⟶ [ ] . \operatorname{Known}(\rho) \longrightarrow[\,],\qquad\operatorname{Var}(v,\rho) \longrightarrow[\,]. Known ( ρ ) ⟶ [ ] , Var ( v , ρ ) ⟶ [ ] . The intended execution retains the left child twice and then makes both children leaves. Its selected leaf counts are ( 1 , 1 , 2 ) (1,1,2) ( 1 , 1 , 2 ) ( 1 , 1 , 0 ) (1,1,0) ( 1 , 1 , 0 ) e = δ = 0 e=\delta=0 e = δ = 0
Table 12.
Both enforcing and choice contributions are zero. The termination rule is justified in Appendix § 8 .6.
Coordinate placement and block assembly
We now place the selected operation and the waiting records at numerical bases, then merge their local leaf data into the working table.
Assigning bases and inserting movements. Set P = 4 ( n + m ) + 64 P=4(n+m)+64 P = 4 ( n + m ) + 64 q q q U U U ρ + 1 \rho+1 ρ + 1 ρ \rho ρ
ρ j ′ = U + 256 P + 256 ( j − 1 ) ( 1 ≤ j ≤ q ) . \rho'_j=U+256P+256(j-1)\qquad(1\leq j\leq q). ρ j ′ = U + 256 P + 256 ( j − 1 ) ( 1 ≤ j ≤ q ) . Move entries to these targets from right to left, using one-unit Move blocks; all other records wait during each such block. Here P P P 256 P 256P 256 P § 2 bounds the total movement.
For a Check, then translate the lower input until its base is three below the upper input’s base. For a Pass, translate the lower known input until its base is one below the upper input’s base. Start the selected operation immediately after this preparation. The placement moves do not trigger new placements. All targets, types, and output bases are updated symbolically, without choosing graph bits.
The following guarantee is the reason for the spacing rule. It will let us apply the local score bounds to an arbitrary candidate tree at its first incorrect block. Here the enforcing score is the sum of the temporary contributions of the selected operation and outside waits, before the final priority multipliers are applied.
Lemma 3.1. Suppose that a scheduled block begins with its prescribed input coordinates. Every complete sequence satisfying its leaf counts and intervals decomposes into sequences satisfying the leaf data of the active operation and of each outside waiting vertex. The local enforcing-score bounds therefore add: every feasible block has at least its intended score, with a gap of at least one for any sequence that is not intended.
Appendix § 8 .7 proves this guarantee, including the small gaps used while moving records. Appendix B.§ 2 verifies the placement invariants and bounds the total construction size.
Appending a block to the working table. Suppose the block starts at depth h h h q q q p p p α j \alpha_j α j γ j \gamma_j γ j j j j q − p q-p q − p
n h + j = α j + ( q − p ) , I h + j = γ j + ( q − p ) . n_{h+j} = \alpha_j + (q-p), \qquad I_{h+j} = \gamma_j + (q-p). n h + j = α j + ( q − p ) , I h + j = γ j + ( q − p ) . To write that row, take the selected template’s entries and the waiting entries at level j j j k = 1 , … , n h + j k=1,\ldots,n_{h+j} k = 1 , … , n h + j q − p q-p q − p
The first copy in the running example. At step 3 of the K 4 − b d K_4-bd K 4 − b d § 3.1.2 , after the preceding coordinate placement, let the current records at depth h h h
[ Z , A a ] = [ Known ( s ) , Var ( a , ρ ) ] , ρ = s + 256. [Z,A_a] = [\operatorname{Known}(s),\operatorname{Var}(a,\rho)], \qquad\rho=s+256. [ Z , A a ] = [ Known ( s ) , Var ( a , ρ )] , ρ = s + 256. Only A a A_a A a s + 1 s+1 s + 1
( n h + 1 , … , n h + 6 ) = ( 1 , 1 , 1 , 1 , 31 , 3 ) , (n_{h+1},\ldots,n_{h+6}) = (1,1,1,1,31,3), ( n h + 1 , … , n h + 6 ) = ( 1 , 1 , 1 , 1 , 31 , 3 ) , ( I h + 1 , … , I h + 6 ) = ( 3 , 5 , 9 , 17 , 3 , 3 ) . (I_{h+1},\ldots,I_{h+6}) = (3,5,9,17,3,3). ( I h + 1 , … , I h + 6 ) = ( 3 , 5 , 9 , 17 , 3 , 3 ) . For example, the first row has two continuing children from copying and one from waiting. At the fourth row, it has sixteen from copying and one from waiting. These temporary internal vertices are part of the selected construction, not additional records that should independently wait. At depth h + 6 h+6 h + 6
[ Known ( s ) , Var ( a , ρ + 1 ) , Var ( a , ρ + 5 ) ] . [\operatorname{Known}(s),\operatorname{Var}(a,\rho+1),\operatorname{Var}(a,\rho+5)]. [ Known ( s ) , Var ( a , ρ + 1 ) , Var ( a , ρ + 5 )] . All three outputs are at this same depth. The emitted leaves remain at their respective depths, and only the three continuing vertices are expanded by the next block. For the two input values, the input and continuing output coordinates are
b a = 0 : ( s , ρ ) ⟼ ( s , ρ + 1 , ρ + 5 ) , b a = 1 : ( s , ρ + 1 ) ⟼ ( s , ρ + 2 , ρ + 6 ) . \begin{aligned}
b_a = 0 &: \quad(s,\rho) \longmapsto(s,\rho+1,\rho+5),\\
b_a = 1 &: \quad(s,\rho+1) \longmapsto(s,\rho+2,\rho+6).
\end{aligned} b a = 0 b a = 1 : ( s , ρ ) ⟼ ( s , ρ + 1 , ρ + 5 ) , : ( s , ρ + 1 ) ⟼ ( s , ρ + 2 , ρ + 6 ) . The gap ρ − s = 256 \rho-s=256 ρ − s = 256 Table 5 shows the coordinates produced by an intended execution. For example, the last row’s sorted coordinates become ( s + 1 , ρ , ρ + 6 ) (s+1,\rho,\rho+6) ( s + 1 , ρ , ρ + 6 ) b a = 0 b_a=0 b a = 0 ( s + 1 , ρ + 1 , ρ + 7 ) (s+1,\rho+1,\rho+7) ( s + 1 , ρ + 1 , ρ + 7 ) b a = 1 b_a=1 b a = 1
Table 5. The complete working rows of the first Copy block, including its waiting reserve. Every rank in a displayed range is a separate leaf position. Global depth is t = h + j t=h+j t = h + j
The next graph-level instruction copies the rightmost of the two variable records, after its own coordinate placement. During that six-level block, the reserve and the other variable record are outside waits. If the latter’s prescribed base is ρ ′ \rho' ρ ′ [ ρ ′ + 1 , ρ ′ + 2 ] [\rho'+1,\rho'+2] [ ρ ′ + 1 , ρ ′ + 2 ] ( 5 , − 1 , − 1 , − 1 , − 1 , − 1 ) (5,-1,-1,-1,-1,-1) ( 5 , − 1 , − 1 , − 1 , − 1 , − 1 ) ρ ′ + 1 + b a \rho'+1+b_a ρ ′ + 1 + b a
Repeating this assembly instruction by instruction produces the working rows for depths 1 , … , H 1,\ldots,H 1 , … , H I H = 0 I_H=0 I H = 0 n t n_t n t u t , k u_{t,k} u t , k
Generating the intermediate target instance from the intermediate code
The working table already specifies the number n t n_t n t t t t n t = 0 n_t=0 n t = 0 N = ∑ t = 1 H n t N=\sum_{t=1}^{H}n_t N = ∑ t = 1 H n t ( ℓ t , k , r t , k , e t , k , δ t , k ) (\ell_{t,k},r_{t,k},e_{t,k},\delta_{t,k}) ( ℓ t , k , r t , k , e t , k , δ t , k ) u t , k u_{t,k} u t , k
Number the expanded instruction blocks 1 , … , J 1,\ldots,J 1 , … , J i ( t ) i(t) i ( t ) t t t
E i = ∑ t : i ( t ) = i ∑ k = 1 n t ∣ e t , k ∣ ( 1 ≤ i ≤ J ) . E_i=\sum_{t:i(t)=i}\sum_{k=1}^{n_t}|e_{t,k}| \qquad(1\le i\le J). E i = t : i ( t ) = i ∑ k = 1 ∑ n t ∣ e t , k ∣ ( 1 ≤ i ≤ J ) . There is exactly one original-choice marker for each graph vertex, so ∑ t , k δ t , k = n \sum_{t,k}\delta_{t,k}=n ∑ t , k δ t , k = n n = ∣ V ( G ) ∣ n=|V(G)| n = ∣ V ( G ) ∣
A ∗ = 1 + max { n , E 1 , … , E J } , B = 2 H A ∗ + 2. A_* = 1+\max\{n,E_1,\ldots,E_J\},\qquad B=2HA_*+2. A ∗ = 1 + max { n , E 1 , … , E J } , B = 2 H A ∗ + 2. The absolute values ensure that positive and negative enforcing coefficients both contribute to the common scale.
For each position, compute the interval coefficient supplied by Lemma A.1 :
g t , k = − 2 H − t ( ℓ t , k + r t , k + H − t ) . (2) g_{t,k}=-2^{H-t}(\ell_{t,k}+r_{t,k}+H-t). \tag*{(2)} g t , k = − 2 H − t ( ℓ t , k + r t , k + H − t ) . (2) Then output
u t , k = B J + 1 g t , k + B J − i ( t ) + 1 e t , k + δ t , k . (3) u_{t,k}=B^{J+1}g_{t,k}+B^{J-i(t)+1}e_{t,k}+\delta_{t,k}. \tag*{(3)} u t , k = B J + 1 g t , k + B J − i ( t ) + 1 e t , k + δ t , k . (3) Thus the interval contribution has the common multiplier B J + 1 B^{J+1} B J + 1 i i i B J − i + 1 B^{J-i+1} B J − i + 1 without a block multiplier. These powers encode lexicographic priorities: interval compliance first, then instruction correctness in temporal order, and finally the independent-set reward. The weight-dominance principle is standard; see, for example, Boolean multilevel optimization [3 ] . For our signed score components, Appendix B.5 proves that a unit increase at one priority outweighs every possible saving below it. Once B B B
The resulting leaf-profile instance is
I G = ( ( n t ) t = 1 H , ( u t , k ) 1 ≤ t ≤ H , 1 ≤ k ≤ n t ) . \mathcal{I}_G=\left((n_t)_{t=1}^{H},(u_{t,k})_{1\le t\le H,\,1\le k\le n_t}\right). I G = ( ( n t ) t = 1 H , ( u t , k ) 1 ≤ t ≤ H , 1 ≤ k ≤ n t ) . Each coefficient remains attached to its existing sorted-coordinate rank ( t , k ) (t,k) ( t , k ) e t , k = δ t , k = 0 e_{t,k}=\delta_{t,k}=0 e t , k = δ t , k = 0 I G \mathcal{I}_G I G § 3 proves that these rows are nonincreasing and that their computation and binary encoding have polynomial size. The following substitution illustrates the arithmetic; we then specify the reference value needed for the decision threshold.
Computing the output coefficients. A first scan of the working table counts its row lengths and accumulates E i E_i E i A ∗ A_* A ∗ B B B (2) and (3) at every position, retaining the row order.
Continuing the Copy example. Abbreviate the multipliers by Ω = B J + 1 \Omega=B^{J+1} Ω = B J + 1 ω i = B J − i + 1 \omega_i=B^{J-i+1} ω i = B J − i + 1 § 3.1.4 , the only outside record is the known reserve. The block has 38 leaf positions, all markers are zero, and its only nonzero enforcing coefficients are 1 1 1 − 1 -1 − 1 E i = ∣ 1 ∣ + ∣ − 1 ∣ = 2 E_i=|1|+|-1|=2 E i = ∣1∣ + ∣ − 1∣ = 2 B B B
Retain the earlier notation: the reserve base is s s s ρ = s + 256 \rho=s+256 ρ = s + 256 t = h + 6 t=h+6 t = h + 6 p = H − t p=H-t p = H − t
( [ s + 1 , s + 1 ] , 0 , 0 ) , ( [ ρ , ρ + 1 ] , 1 , 0 ) , ( [ ρ + 6 , ρ + 7 ] , − 1 , 0 ) . ([s+1,s+1],0,0),\qquad([\rho,\rho+1],1,0),\qquad([\rho+6,\rho+7],-1,0). ([ s + 1 , s + 1 ] , 0 , 0 ) , ([ ρ , ρ + 1 ] , 1 , 0 ) , ([ ρ + 6 , ρ + 7 ] , − 1 , 0 ) . Substitution gives
u t , 1 = − Ω 2 p ( 2 s + 2 + p ) , u_{t,1}=-\Omega2^p(2s+2+p), u t , 1 = − Ω 2 p ( 2 s + 2 + p ) , u t , 2 = − Ω 2 p ( 2 ρ + 1 + p ) + ω i , u_{t,2}=-\Omega2^p(2\rho+1+p)+\omega_i, u t , 2 = − Ω 2 p ( 2 ρ + 1 + p ) + ω i , u t , 3 = − Ω 2 p ( 2 ρ + 13 + p ) − ω i . u_{t,3}=-\Omega2^p(2\rho+13+p)-\omega_i. u t , 3 = − Ω 2 p ( 2 ρ + 13 + p ) − ω i . The reserve entry has e = δ = 0 e=\delta=0 e = δ = 0 [ ρ v , ρ v + 1 ] [\rho_v,\rho_v+1] [ ρ v , ρ v + 1 ] e = 0 e=0 e = 0 δ = 1 \delta=1 δ = 1
− Ω 2 H − t ( 2 ρ v + 1 + H − t ) + 1. -\Omega2^{H-t}(2\rho_v+1+H-t)+1. − Ω 2 H − t ( 2 ρ v + 1 + H − t ) + 1. Its final + 1 +1 + 1 ω i ( t ) \omega_i(t) ω i ( t )
The reference value and the decision threshold. For each block i i i s i s_i s i Table 4 . These are fixed constants: − 6 -6 − 6 − 1 -1 − 1 ρ v \rho_v ρ v v v v
Compute I 0 = 1 I_0=1 I 0 = 1 I t = 2 I t − 1 − n t I_t=2I_{t-1}-n_t I t = 2 I t − 1 − n t
Q 0 = − ∑ t = 0 H − 1 I t 2 H − t − 1 ( H − t ) − ∑ t = 1 H ∑ k = 1 n t 2 H − t ℓ t , k r t , k . (4) Q_0=-\sum_{t=0}^{H-1}I_t2^{H-t-1}(H-t)-\sum_{t=1}^{H}\sum_{k=1}^{n_t}2^{H-t}\ell_{t,k}r_{t,k}. \tag*{(4)} Q 0 = − t = 0 ∑ H − 1 I t 2 H − t − 1 ( H − t ) − t = 1 ∑ H k = 1 ∑ n t 2 H − t ℓ t , k r t , k . (4) and then
C = B J + 1 Q 0 + ∑ i = 1 J B J − i + 1 s i + ∑ v ∈ V ( ρ v + 1 ) . (5) C=B^{J+1}Q_0+\sum_{i=1}^{J}B^{J-i+1}s_i+\sum_{v\in V}(\rho_v+1). \tag*{(5)} C = B J + 1 Q 0 + i = 1 ∑ J B J − i + 1 s i + v ∈ V ∑ ( ρ v + 1 ) . (5) These are arithmetic expressions in the completed working table. For a source decision instance ( G , k ) (G,k) ( G , k ) I G \mathcal{I}_G I G τ = C − k \tau=C-k τ = C − k § 4 identifies C C C
Execution: from an independent set to a feasible tree
Fix the instance I G \mathcal{I}_G I G § 3.1 . Its leaf counts and final coefficients u t , k u_{t,k} u t , k G G G S ⊆ V ( G ) S\subseteq V(G) S ⊆ V ( G ) b v = 1 b_v=1 b v = 1 v ∈ S v\in S v ∈ S b v = 0 b_v=0 b v = 0
At the original Choose( v ) (v) ( v ) b v b_v b v ( v , ρ ) (v,\rho) ( v , ρ ) ρ + b v \rho+b_v ρ + b v X t X_t X t
L t = E ( X t − 1 ) − X t , z t , 1 ≤ ⋯ ≤ z t , n t , L_t=\mathcal{E}(X_{t-1})-X_t,\qquad z_{t,1}\leq\cdots\leq z_{t,n_t}, L t = E ( X t − 1 ) − X t , z t , 1 ≤ ⋯ ≤ z t , n t , where the z t , k z_{t,k} z t , k L t L_t L t ρ + 1 + b v \rho+1+b_v ρ + 1 + b v ρ v \rho_v ρ v ρ v + 1 − b v \rho_v+1-b_v ρ v + 1 − b v
Every edge check receives the choices of its two endpoints. Independence ensures that no check receives 11, so all blocks admit their prescribed continuations. After the final termination, X H = ∅ X_H=\varnothing X H = ∅
The realization procedure of § 2 therefore produces a full ordered binary tree T S T_S T S z t , k ( T S ) z_{t,k}(T_S) z t , k ( T S ) ∑ t , k u t , k z t , k ( T S ) \sum_{t,k} u_{t,k}z_{t,k}(T_S) ∑ t , k u t , k z t , k ( T S )
The execution determines a coordinate profile, not necessarily a unique concrete tree . Choosing different occurrences of equal-coordinate children can yield different realizations. Every realization has the same sorted leaf lists and therefore the same feasibility, interval-compliance status, and score. We may choose any one, or fix a deterministic rule for these choices, and denote the resulting tree by T S T_S T S
The reference score and the forward correspondence. Let T 0 : = T ∅ T_0 := T_{\varnothing} T 0 := T ∅ C C C (5) . This integer is independent of S S S S S S
score ( T S ) = C − ∣ S ∣ ≤ C . (6) \operatorname{score}(T_S) = C - |S| \le C. \tag*{(6)} score ( T S ) = C − ∣ S ∣ ≤ C . (6) The interval contribution and each block’s enforcing contribution are constant across intended executions. Only the original-choice terms vary: the term for v v v ρ v + 1 \rho_v + 1 ρ v + 1 ρ v + 1 − b v \rho_v + 1 - b_v ρ v + 1 − b v − ∣ S ∣ -|S| − ∣ S ∣ § 4 supplies the realization details and verifies the reference formula (5) . In our running example K 4 − b d K_4 - bd K 4 − b d S = { b , d } S = \{b,d\} S = { b , d } ( b a , b b , b c , b d ) = ( 0 , 1 , 0 , 1 ) (b_a,b_b,b_c,b_d) = (0,1,0,1) ( b a , b b , b c , b d ) = ( 0 , 1 , 0 , 1 ) C − 2 C - 2 C − 2 C C C a b ab ab a c ac a c b c bc b c a d ad a d c d cd c d
Assignments that are not independent. For an arbitrary assignment b b b S b = { v : b v = 1 } S_b = \{v : b_v = 1\} S b = { v : b v = 1 } S b S_b S b Lemma A.3 ). The program and output instance remain unchanged; it is this attempted execution that fails. In the running example, choosing { a , b } \{a,b\} { a , b } a b ab ab C − 1 C - 1 C − 1 § 3.3 will show that every feasible tree of score at most C C C
From a feasible tree of the leaf-profile problem back to an independent set
§ 3.2 supplies the all-zero realization T 0 = T ∅ T_0 = T_{\varnothing} T 0 = T ∅ L G \mathcal{L}_G L G C = score ( T 0 ) C = \operatorname{score}(T_0) C = score ( T 0 ) OPT t r e e ( L G ) ≤ C \operatorname{OPT}_{\mathrm{tree}}(\mathcal{L}_G) \le C OPT tree ( L G ) ≤ C C C C arbitrary full ordered tree T T T C C C § 3.3.2 will establish instruction correctness and recover the independent set.
Leaf compliance from the interval identity
A traversal of T T T z t , 1 ( T ) , … , z t , n t ( T ) z_{t,1}(T), \ldots, z_{t,n_t}(T) z t , 1 ( T ) , … , z t , n t ( T ) § 2.2 , with repetitions retained. We can therefore compute score ( T ) = ∑ t , k u t , k z t , k ( T ) \operatorname{score}(T) = \sum_{t,k} u_{t,k}z_{t,k}(T) score ( T ) = ∑ t , k u t , k z t , k ( T )
The auxiliary intervals from the working table are not feasibility constraints of the target problem. Call T T T leaf-compliant if ℓ t , k ≤ z t , k ( T ) ≤ r t , k \ell_{t,k} \le z_{t,k}(T) \le r_{t,k} ℓ t , k ≤ z t , k ( T ) ≤ r t , k § 3.2 . We now show that the score bound forces it for an arbitrary candidate tree:
score ( T ) ≤ C ⇒ T is leaf-compliant. (7) \operatorname{score}(T) \le C \quad\Rightarrow\quad T\text{ is leaf-compliant.} \tag*{(7)} score ( T ) ≤ C ⇒ T is leaf-compliant. (7) Why the score forces compliance. Let Q ( T ) = ∑ t , k q t , k z t , k ( T ) Q(T)=\sum_{t,k}q_{t,k}z_{t,k}(T) Q ( T ) = ∑ t , k q t , k z t , k ( T ) § 3.1.5 , and let Q 0 Q_0 Q 0 (4) , which equals Q ( T 0 ) Q(T_0) Q ( T 0 )
Q ( T ) − Q 0 = ∑ t , k 2 H − t ( z t , k ( T ) − ℓ t , k ) ( z t , k ( T ) − r t , k ) . (8) Q(T)-Q_0=\sum_{t,k}2^{H-t}\bigl(z_{t,k}(T)-\ell_{t,k}\bigr)\bigl(z_{t,k}(T)-r_{t,k}\bigr). \tag*{(8)} Q ( T ) − Q 0 = t , k ∑ 2 H − t ( z t , k ( T ) − ℓ t , k ) ( z t , k ( T ) − r t , k ) . (8) Every summand is a nonnegative integer and vanishes exactly when its interval holds, because the interval has integer endpoints and width zero or one. A single violation therefore gives Q ( T ) − Q 0 ≥ 1 Q(T)-Q_0\ge1 Q ( T ) − Q 0 ≥ 1 linear scores on the left.
The final coefficients multiply Q Q Q B J + 1 B^{J+1} B J + 1 J J J B J , … , B , 1 B^J,\ldots,B,1 B J , … , B , 1 2 H A ∗ 2HA_* 2 H A ∗ T T T T 0 T_0 T 0 [ 0 , H ] [0,H] [ 0 , H ] A ∗ A_* A ∗
score ( T ) − C ≥ B J + 1 − 2 H A ∗ ∑ j = 0 J B j > 0 , (9) \operatorname{score}(T)-C\ge B^{J+1}-2HA_*\sum_{j=0}^{J}B^j>0, \tag*{(9)} score ( T ) − C ≥ B J + 1 − 2 H A ∗ j = 0 ∑ J B j > 0 , (9) where B = 2 H A ∗ + 2 B=2HA_*+2 B = 2 H A ∗ + 2 (7) holds without assuming any intended instruction behavior. Leaf compliance is only the first step: it does not yet show that T T T
Instruction correctness: compatibility with an intended execution
Let T T T score ( T ) ≤ C \operatorname{score}(T)\le C score ( T ) ≤ C § 3.3.1 it is leaf-compliant. We show that its coordinate profile follows the fixed program for an independent-set assignment; leaf compliance alone does not establish this.
Aligning the tree with the program. Use the fixed boundaries of § 3.1.3 to assign leaf depths h i − 1 + 1 , … , h i h_{i-1}+1,\ldots,h_i h i − 1 + 1 , … , h i i i i ( t v , k v ) (t_v,k_v) ( t v , k v ) ( v ) (v) ( v ) ρ v \rho_v ρ v [ ρ v , ρ v + 1 ] [\rho_v,\rho_v+1] [ ρ v , ρ v + 1 ] b v = ρ v + 1 − z t v , k v ( T ) ∈ { 0 , 1 } b_v=\rho_v+1-z_{t_v,k_v}(T)\in\{0,1\} b v = ρ v + 1 − z t v , k v ( T ) ∈ { 0 , 1 } i i i intended for these bits if its complete sequence of internal-coordinate multisets X h i − 1 ( T ) , … , X h i ( T ) X_{h_{i-1}}(T),\ldots,X_{h_i}(T) X h i − 1 ( T ) , … , X h i ( T )
Why the internal scores apply to the given tree. Let f i ( T ) f_i(T) f i ( T ) e t , k z t , k ( T ) e_{t,k}z_{t,k}(T) e t , k z t , k ( T ) i i i f 0 ( T ) = ∑ t , k δ t , k z t , k ( T ) f_0(T)=\sum_{t,k}\delta_{t,k}z_{t,k}(T) f 0 ( T ) = ∑ t , k δ t , k z t , k ( T ) § 3.1.5 gives the exact identity
score ( T ) = B J + 1 Q ( T ) + ∑ i = 1 J B J − i + 1 f i ( T ) + f 0 ( T ) . (10) \operatorname{score}(T)=B^{J+1}Q(T)+\sum_{i=1}^{J}B^{J-i+1}f_i(T)+f_0(T). \tag*{(10)} score ( T ) = B J + 1 Q ( T ) + i = 1 ∑ J B J − i + 1 f i ( T ) + f 0 ( T ) . (10) It holds for every candidate, using its actual sorted coordinates at the same ranks. The working table can be retained or recomputed from G G G u u u Q ( T ) = Q ( T 0 ) Q(T)=Q(T_0) Q ( T ) = Q ( T 0 ) total interval contribution, not necessarily its contribution within each block.
Excluding the first discrepancy. Suppose block i i i Lemma 3.1 gives f i ( T ) ≥ s i + 1 f_i(T) \ge s_i+1 f i ( T ) ≥ s i + 1 s i s_i s i § 8 proves the underlying local statements. Earlier correct blocks satisfy f j ( T ) = s j = f j ( T 0 ) f_j(T)=s_j=f_j(T_0) f j ( T ) = s j = f j ( T 0 ) f 0 f_0 f 0 2 H A ∗ 2H A_* 2 H A ∗ q = J − i + 1 q=J-i+1 q = J − i + 1
score ( T ) − C ≥ B q − 2 H A ∗ ∑ a = 0 q − 1 B a > 0 , (11) \operatorname{score}(T)-C \ge B^q-2H A_*\sum_{a=0}^{q-1}B^a>0, \tag*{(11)} score ( T ) − C ≥ B q − 2 H A ∗ a = 0 ∑ q − 1 B a > 0 , (11) since B − 1 = 2 H A ∗ + 1 B-1=2H A_*+1 B − 1 = 2 H A ∗ + 1
Recovering the independent set. Set S T = { v : b v = 1 } S_T=\{v:b_v=1\} S T = { v : b v = 1 } S T S_T S T T 0 T_0 T 0
score ( T ) = C − ∣ S T ∣ . (12) \operatorname{score}(T)=C-\lvert S_T\rvert. \tag*{(12)} score ( T ) = C − ∣ S T ∣ . (12) The assignment replays the observed lists, whose concrete tree realizations are score-equivalent. Recovery is polynomial-time; Appendix B.6 gives the concrete-tree replay and recovery procedure.
Guarantees of the first reduction
For a simple planar graph G G G n = ∣ V ( G ) ∣ n=\lvert V(G)\rvert n = ∣ V ( G )∣
Lemma 3.2. Given G G G
min T score ( T ) = C − α ( G ) , \min_T \operatorname{score}(T)=C-\alpha(G), T min score ( T ) = C − α ( G ) , where C C C H = O ( n 4 ) H=O(n^4) H = O ( n 4 ) N = O ( n 5 ) N=O(n^5) N = O ( n 5 )
Proof. By § 3.2 , every independent set S S S C − ∣ S ∣ C-\lvert S\rvert C − ∣ S ∣ C C C § 3.3 . That argument recovers an independent set S T S_T S T score ( T ) = C − ∣ S T ∣ \operatorname{score}(T)=C-\lvert S_T\rvert score ( T ) = C − ∣ S T ∣
The height and leaf bounds follow from Appendix B.§ 2 ; Appendix B.§ 3 proves that the coefficient rows are nonincreasing and that the construction and its binary encoding have polynomial size. □
For 0 ≤ k ≤ n 0 \le k \le n 0 ≤ k ≤ n G G G k k k C − k C-k C − k C − k C-k C − k k k k
For the running graph K 4 − b d K_4-bd K 4 − b d (12) implies that a tree of score C − 2 C-2 C − 2 { b , d } \{b,d\} { b , d } C − 2 C-2 C − 2
From leaf scores to letter costs
Having constructed the leaf-profile instance, we now give the second reduction, from the leaf-profile problem to binary prefix coding. The conversion applies to any feasible instance of the intermediate problem, independently of the graph construction in § 3 .
The intermediate problem permits signed coefficients and fixes the leaf counts, whereas ordinary coding requires positive frequencies and leaves both symbol depths and assignments unrestricted. We use two scales to bridge these differences. A large dyadic addition to each coefficient makes the frequencies positive and forces the prescribed symbol depths; a second scale in the letter costs gives weighted length priority over right turns.
Constructing the coding instance
Let I \mathcal{I} I H H H n 1 , … , n H n_1,\ldots,n_H n 1 , … , n H n H > 0 n_H>0 n H > 0
u t , 1 ≥ ⋯ ≥ u t , n t ( 1 ≤ t ≤ H ) u_{t,1} \ge\cdots\ge u_{t,n_t} \qquad(1 \le t \le H) u t , 1 ≥ ⋯ ≥ u t , n t ( 1 ≤ t ≤ H ) be its integer coefficient rows. There are N = ∑ t n t ≥ 2 N=\sum_t n_t \ge2 N = ∑ t n t ≥ 2 ( t , k ) (t,k) ( t , k )
j ( t , k ) = ∑ s < t n s + k , d j ( t , k ) = t , θ j ( t , k ) = u t , k . j(t,k)=\sum_{s<t} n_s+k,\qquad d_{j(t,k)}=t,\qquad\theta_{j(t,k)}=u_{t,k}. j ( t , k ) = s < t ∑ n s + k , d j ( t , k ) = t , θ j ( t , k ) = u t , k . Here d j d_j d j
A = ∑ j = 1 N ∣ θ j ∣ , Γ = N A + 1 , A=\sum_{j=1}^{N}|\theta_j|,\qquad\Gamma=NA+1, A = j = 1 ∑ N ∣ θ j ∣ , Γ = N A + 1 , and define
w j = Γ 2 H − d j + θ j . (13) w_j=\Gamma2^{H-d_j}+\theta_j. \tag*{(13)} w j = Γ 2 H − d j + θ j . (13) The profile determines I 0 = 1 I_0=1 I 0 = 1 I t = 2 I t − 1 − n t I_t=2I_{t-1}-n_t I t = 2 I t − 1 − n t
W = ∑ j w j , L 0 = ∑ j w j d j , W=\sum_j w_j,\qquad L_0=\sum_j w_jd_j, W = j ∑ w j , L 0 = j ∑ w j d j , M = ( N − 1 ) W + 1 , B 0 = ∑ t = 0 H − 1 I t Γ 2 H − t − 1 , M=(N-1)W+1,\qquad B_0=\sum_{t=0}^{H-1} I_t\Gamma2^{H-t-1}, M = ( N − 1 ) W + 1 , B 0 = t = 0 ∑ H − 1 I t Γ 2 H − t − 1 , and put β = M L 0 + B 0 \beta=ML_0+B_0 β = M L 0 + B 0 L 0 L_0 L 0 B 0 B_0 B 0 J \mathcal{J} J w 1 , … , w N w_1,\ldots,w_N w 1 , … , w N ( M , M + 1 ) (M,M+1) ( M , M + 1 ) β \beta β
For a feasible source tree T T T canonical code C T C_T C T t t t j ( t , k ) j(t,k) j ( t , k ) k k k
A three-symbol example
Take n 1 = 1 n_1=1 n 1 = 1 n 2 = 2 n_2=2 n 2 = 2 ( 0 ) (0) ( 0 ) ( 2 , − 1 ) (2,-1) ( 2 , − 1 )
( d 1 , d 2 , d 3 ) = ( 1 , 2 , 2 ) , ( θ 1 , θ 2 , θ 3 ) = ( 0 , 2 , − 1 ) , Γ = 10 , (d_1,d_2,d_3)=(1,2,2),\qquad(\theta_1,\theta_2,\theta_3)=(0,2,-1),\qquad\Gamma=10, ( d 1 , d 2 , d 3 ) = ( 1 , 2 , 2 ) , ( θ 1 , θ 2 , θ 3 ) = ( 0 , 2 , − 1 ) , Γ = 10 , so the frequencies are ( 20 , 12 , 9 ) (20,12,9) ( 20 , 12 , 9 ) W = 41 W=41 W = 41 M = 83 M=83 M = 83 L 0 = 62 L_0=62 L 0 = 62 B 0 = 30 B_0=30 B 0 = 30 β = 5176 \beta=5176 β = 5176 ( 0 , 10 , 11 ) (0,10,11) ( 0 , 10 , 11 ) ( 1 , 00 , 01 ) (1,00,01) ( 1 , 00 , 01 ) 0 0 0 − 1 -1 − 1 h j = ∣ C j ∣ h_j=|C_j| h j = ∣ C j ∣ z j = ∣ C j ∣ 1 z_j=|C_j|_1 z j = ∣ C j ∣ 1 j j j L = ∑ j w j h j L=\sum_j w_jh_j L = ∑ j w j h j R = ∑ j w j z j R=\sum_j w_jz_j R = ∑ j w j z j 83 L + R 83L+R 83 L + R
Table 1 (PDF p. 32).
The third row reverses the two depth-two labels of the second row, increasing the cost without changing the underlying tree. Thus even after depths are fixed, the symbol assignment matters. The fourth places a symbol at an incorrect depth. Its coefficient contribution ∑ j θ j z j = − 2 \sum_j\theta_jz_j=-2 ∑ j θ j z j = − 2 § 4.3 compares with all competing codes and shows that no other code is cheaper than ( 1 , 00 , 01 ) (1,00,01) ( 1 , 00 , 01 ) 5175 − 5176 = − 1 5175-5176=-1 5175 − 5176 = − 1 τ = − 1 \tau=-1 τ = − 1 K = 5175 K=5175 K = 5175
Guarantees and proof
The construction preserves the optimum and permits recovery in both directions.
Lemma 4.1. The frequencies in (13) are positive integers. The codes of minimum ordinary weighted length are exactly the codes placing every symbol j j j d j d_j d j B 0 + OPT t r e e ( I ) B_0+\operatorname{OPT}_{\mathrm{tree}}(\mathcal{I}) B 0 + OPT tree ( I ) ( M , M + 1 ) (M,M+1) ( M , M + 1 )
OPT c o d e ( J ) = β + OPT t r e e ( I ) . (14) \operatorname{OPT}_{\mathrm{code}}(\mathcal{J})=\beta+\operatorname{OPT}_{\mathrm{tree}}(\mathcal{I}). \tag*{(14)} OPT code ( J ) = β + OPT tree ( I ) . (14) For every source-feasible ordered tree T T T
cost ( C T ) = β + score ( T ) . (15) \operatorname{cost}(C_T)=\beta+\operatorname{score}(T). \tag*{(15)} cost ( C T ) = β + score ( T ) . (15) The canonical map sends every optimal source tree to an optimal code. Conversely, forgetting the symbol labels of any optimal code yields an optimal source tree. The instance construction and both
solution maps take polynomial time, and all constructed numbers have polynomial binary encoding length.
The depth-forcing step is a dyadic instance of classical source coding: p j = 2 − d j p_j = 2^{-d_j} p j = 2 − d j [24 ] , and d j = − log 2 p j d_j = -\log_2 p_j d j = − log 2 p j [30 ] . The proof below gives an elementary integer gap and shows why the same dyadic terms contribute a constant to the right-edge objective.
Proof of Lemma 4.1 . Since 2 H − d j ≥ 1 2^{H-d_j} \ge1 2 H − d j ≥ 1 Γ > A \Gamma> A Γ > A § 2.1 , every optimum is full and every nonfull competitor can be improved to a full one, for both ordinary weighted length and coding cost. A full tree with N N N N − 1 N-1 N − 1 N − 1 N-1 N − 1 H ≤ N − 1 H \le N-1 H ≤ N − 1
The frequencies force the prescribed depths. Let h j h_j h j j j j [24 ] , applied to the prescribed and actual depth sequences, gives
∑ j 2 − d j = ∑ j 2 − h j = 1. (16) \sum_j 2^{-d_j} = \sum_j 2^{-h_j} = 1. \tag*{(16)} j ∑ 2 − d j = j ∑ 2 − h j = 1. (16) For every integer s s s s ≥ 1 − 2 − s s \ge1 - 2^{-s} s ≥ 1 − 2 − s s > 0 s > 0 s > 0 s ≥ 0 s \ge0 s ≥ 0 s = − k < 0 s=-k<0 s = − k < 0 2 k ≥ k + 1 2^k \ge k+1 2 k ≥ k + 1 s = h j − d j s=h_j-d_j s = h j − d j 2 − d j 2^{-d_j} 2 − d j
∑ j 2 − d j ( h j − d j ) ≥ ∑ j ( 2 − d j − 2 − h j ) = 0. \sum_j 2^{-d_j}(h_j-d_j) \ge\sum_j (2^{-d_j}-2^{-h_j}) = 0. j ∑ 2 − d j ( h j − d j ) ≥ j ∑ ( 2 − d j − 2 − h j ) = 0. If the depth vectors differ, some depth must increase: otherwise every h j ≤ d j h_j \le d_j h j ≤ d j (16) . The displayed inequality is therefore strict whenever the vectors differ. Multiplying by 2 H 2^H 2 H
∑ j 2 H − d j ( h j − d j ) ≥ 1 if some h j ≠ d j . \sum_j 2^{H-d_j}(h_j-d_j) \ge1 \qquad\text{if some } h_j \ne d_j. j ∑ 2 H − d j ( h j − d j ) ≥ 1 if some h j = d j . Write L = ∑ j w j h j L=\sum_j w_jh_j L = ∑ j w j h j N − 1 N-1 N − 1
∣ ∑ j θ j ( h j − d j ) ∣ ≤ ( N − 1 ) A . \left|\sum_j \theta_j(h_j-d_j)\right| \le(N-1)A. j ∑ θ j ( h j − d j ) ≤ ( N − 1 ) A . Consequently, a change in any symbol depth gives
L − L 0 = Γ ∑ j 2 H − d j ( h j − d j ) + ∑ j θ j ( h j − d j ) ≥ Γ − ( N − 1 ) A = A + 1 > 0. L-L_0 = \Gamma\sum_j 2^{H-d_j}(h_j-d_j) + \sum_j \theta_j(h_j-d_j) \ge\Gamma-(N-1)A = A+1 > 0. L − L 0 = Γ j ∑ 2 H − d j ( h j − d j ) + j ∑ θ j ( h j − d j ) ≥ Γ − ( N − 1 ) A = A + 1 > 0. Every assignment with h j = d j h_j=d_j h j = d j L 0 L_0 L 0
The letter costs give length priority. Let z j z_j z j j j j R = ∑ j w j z j R=\sum_j w_jz_j R = ∑ j w j z j ( M , M + 1 ) (M,M+1) ( M , M + 1 )
cost ( C ) = M L + R , 0 ≤ R ≤ ( N − 1 ) W = M − 1. \operatorname{cost}(C) = ML+R,\qquad0 \le R \le(N-1)W = M-1. cost ( C ) = M L + R , 0 ≤ R ≤ ( N − 1 ) W = M − 1. Since L L L L L L R R R h j = d j h_j=d_j h j = d j j j j R R R t t t
∑ j below the child 2 − ( d j − t − 1 ) = 1. \sum_{j\ \text{below the child}} 2^{-(d_j-t-1)}=1. j below the child ∑ 2 − ( d j − t − 1 ) = 1. The total dyadic weight below that child is therefore Γ 2 H − t − 1 \Gamma2^{H-t-1} Γ 2 H − t − 1 R R R t t t
∑ j Γ 2 H − d j z j = B 0 , cost ( C ) = β + ∑ j θ j z j . \sum_j \Gamma2^{H-d_j}z_j=B_0,\qquad\operatorname{cost}(C)=\beta+\sum_j\theta_jz_j. j ∑ Γ 2 H − d j z j = B 0 , cost ( C ) = β + j ∑ θ j z j . The original profile fixes the counts I t I_t I t B 0 B_0 B 0 Optimal codes and source trees. The sorting observation in § 2.2 shows that, at each depth, the canonical assignment minimizes the coefficient contribution, including when coefficients are negative or coordinates are tied. It follows that the canonical code of every source-feasible tree T T T (15) . For any code C C C T T T
cost ( C ) ≥ β + score ( T ) ≥ β + OPT t r e e ( I ) . (17) \operatorname{cost}(C)\ge\beta+\operatorname{score}(T)\ge\beta+\operatorname{OPT}_{\mathrm{tree}}(\mathcal{I}). \tag*{(17)} cost ( C ) ≥ β + score ( T ) ≥ β + OPT tree ( I ) . (17) Equality throughout is attained by the canonical labeling of any optimal source tree. Thus the minimum weighted number of ones among ordinary minimum-length codes is B 0 + OPT t r e e ( I ) B_0+\operatorname{OPT}_{\mathrm{tree}}(\mathcal{I}) B 0 + OPT tree ( I ) (14) and the forward solution map.
Conversely, any optimal code is full and has these depths, so its underlying tree T T T (17) , forcing equality in both inequalities and hence score ( T ) = OPT t r e e ( I ) \operatorname{score}(T)=\operatorname{OPT}_{\mathrm{tree}}(\mathcal{I}) score ( T ) = OPT tree ( I )
Encoding length and computation. Let b ≥ 1 b\ge1 b ≥ 1 ∣ θ j ∣ < 2 b |\theta_j|<2^b ∣ θ j ∣ < 2 b j j j A < N 2 b A<N2^b A < N 2 b O ( H + b + log N ) O(H+b+\log N) O ( H + b + log N ) W W W M M M L 0 L_0 L 0 B 0 B_0 B 0 β \beta β ∑ t I t = N − 1 \sum_t I_t=N-1 ∑ t I t = N − 1 N N N H ≤ N − 1 H\le N-1 H ≤ N − 1
A source tree has 2 N − 1 2N-1 2 N − 1 N ( N − 1 ) N(N-1) N ( N − 1 )
Decision thresholds. For a source threshold τ \tau τ K = β + τ K=\beta+\tau K = β + τ τ \tau τ K K K (15) . Conversely, if any code has cost at most K K K K − β = τ K-\beta=\tau K − β = τ
The target decision problem requires a nonnegative threshold. If K < 0 K<0 K < 0 τ \tau τ w 1 = w 2 = 1 w_1=w_2=1 w 1 = w 2 = 1 ( 1 , 2 ) (1,2) ( 1 , 2 ) 2 2 2 3 3 3 K = β + τ K=\beta+\tau K = β + τ τ \tau τ
The secondary objective. The length-priority argument also applies to arbitrary positive integer frequencies, independently of the prescribed-profile construction. With W = ∑ j w j W = \sum_j w_j W = ∑ j w j M = ( N − 1 ) W + 1 M = (N - 1)W + 1 M = ( N − 1 ) W + 1
min C cost M , M + 1 ( C ) = M L ∗ ( w ) + R ∗ ( w ) . \min_{\mathcal{C}} \operatorname{cost}_{M,M+1}(\mathcal{C}) = M L^{*}(\mathbf{w}) + R^{*}(\mathbf{w}). C min cost M , M + 1 ( C ) = M L ∗ ( w ) + R ∗ ( w ) . Thus a secondary decision instance ( w , κ ) (\mathbf{w},\kappa) ( w , κ ) ( M , M + 1 ) (M,M+1) ( M , M + 1 ) K = M L ∗ ( w ) + κ K = M L^{*}(\mathbf{w}) + \kappa K = M L ∗ ( w ) + κ L ∗ ( w ) L^{*}(\mathbf{w}) L ∗ ( w )
Completing the NP-completeness proof
Together, Lemmas 3.2 and 4.1 give the two decision reductions.
Proof of Theorem 1.1 . Given an instance ( G , k ) (G,k) ( G , k ) C C C J G \mathcal{J}_G J G ( M , M + 1 ) (M,M+1) ( M , M + 1 ) β \beta β
OPT c o d e ( J G ) = β + C − α ( G ) . (18) \operatorname{OPT}_{\mathrm{code}}(\mathcal{J}_G) = \beta+ C - \alpha(G). \tag*{(18)} OPT code ( J G ) = β + C − α ( G ) . (18) For the decision problem, choose
K = β + C − k . K = \beta+ C - k. K = β + C − k . By (18) , there exists a code of cost at most K K K G G G k k k C C C β \beta β
Trivial values of k k k K K K w 1 = w 2 = 1 w_1 = w_2 = 1 w 1 = w 2 = 1 ( c 0 , c 1 ) = ( 1 , 2 ) (c_0,c_1) = (1,2) ( c 0 , c 1 ) = ( 1 , 2 )
For membership in NP, a full binary tree with N N N 2 N − 1 2N - 1 2 N − 1 § 2.1 , a yes-instance always has such a full-tree certificate: suppressing one-child vertices can only improve its cost. □
Proof of Corollary 1.2. Use the same frequencies. The depth-forcing assertion of Lemma 4.1 shows that the minimum-length codes are exactly those with the prescribed depth of each symbol. Among those codes, the minimum weighted number of ones is
B 0 + OPT t r e e ( I G ) = B 0 + C − α ( G ) . B_0 + \operatorname{OPT}_{\mathrm{tree}}(\mathcal{I}_G) = B_0 + C - \alpha(G). B 0 + OPT tree ( I G ) = B 0 + C − α ( G ) . Thus κ = B 0 + C − k \kappa= B_0 + C - k κ = B 0 + C − k κ < 0 \kappa< 0 κ < 0 w 1 = w 2 = 1 w_1 = w_2 = 1 w 1 = w 2 = 1 κ = 0 \kappa= 0 κ = 0 w 1 = w 2 = 1 w_1 = w_2 = 1 w 1 = w 2 = 1 κ \kappa κ
Consecutive integer letter costs supplied as part of the input suffice for NP-completeness of binary prefix coding. The secondary objective in Corollary 1.2 identifies where the difficulty can remain: Huffman’s algorithm finds the minimum weighted length, but minimizing the weighted number of ones among all codes attaining that length is NP-hard.
The priorities and dyadic terms can have exponentially large values. Thus, the reduction does not settle strong NP-hardness or the existence of a pseudopolynomial-time algorithm. For the secondary problem in Corollary 1.2, a specific question is whether NP-hardness persists when every frequency satisfies w i ≤ N O ( 1 ) w_i \le N^{O(1)} w i ≤ N O ( 1 ) ( N − 1 ) ∑ i w i (N-1)\sum_i w_i ( N − 1 ) ∑ i w i
For ordinary binary prefix coding, a separate question is whether NP-hardness persists when c 1 ≤ N O ( 1 ) c_1 \le N^{O(1)} c 1 ≤ N O ( 1 ) O ( N c 1 ) O(N^{c_1}) O ( N c 1 ) [4 ] is polynomial for fixed c 1 c_1 c 1 c 1 c_1 c 1 N N N [16 ] also remains unresolved by this result.
AI Methodology
Table 13.
Details. The authors initially asked OpenAI’s Codex for an NP-hardness proof for the generalized prefix-coding problem studied in [6 ] . After Codex produced such a proof, the authors asked it to establish hardness first for nonbinary prefix coding and then for binary prefix coding. Codex contributed to the reduction strategy and its mathematical development, including the local tree constructions, their assembly into a tree representation of an independent-set computation, and the conversion to unequal-letter-cost coding.
The authors guided the development, requested corrections and simplifications, and substantially revised the organization and exposition to make the construction and its proofs easier to follow. Codex also assisted with drafting, checking arguments, running finite checks, and developing worked examples. The authors take responsibility for the final statements, proofs, and presentation.
References
Interval constraints and local constructions
The interval identity and local score bounds hold for arbitrary trees with the prescribed leaf data. The local bounds must also allow arbitrary final internal coordinates, so that they apply at the first incorrect block.
Interval constraints
Each leaf position ( t , k ) (t,k) ( t , k ) [ ℓ t , k , r t , k ] [\ell_{t,k}, r_{t,k}] [ ℓ t , k , r t , k ] z z z ( z − ℓ ) ( z − r ) (z-\ell)(z-r) ( z − ℓ ) ( z − r ) r − ℓ ∈ { 0 , 1 } r-\ell\in\{0,1\} r − ℓ ∈ { 0 , 1 }
Lemma A.1. Fix a realizable sequence I 0 , … , I H I_0,\ldots,I_H I 0 , … , I H g t , k g_{t,k} g t , k Q 0 Q_0 Q 0 ( g t , k ) k (g_{t,k})_k ( g t , k ) k
Q ( T ) − Q 0 = ∑ t , k 2 H − t ( z t , k − ℓ t , k ) ( z t , k − r t , k ) , Q ( T ) = ∑ t , k g t , k z t , k . (19) Q(T)-Q_0=\sum_{t,k}2^{H-t}(z_{t,k}-\ell_{t,k})(z_{t,k}-r_{t,k}), \qquad Q(T)=\sum_{t,k}g_{t,k}z_{t,k}. \tag*{(19)} Q ( T ) − Q 0 = t , k ∑ 2 H − t ( z t , k − ℓ t , k ) ( z t , k − r t , k ) , Q ( T ) = t , k ∑ g t , k z t , k . (19) Consequently, Q ( T ) ≥ Q 0 Q(T)\ge Q_0 Q ( T ) ≥ Q 0
The proof uses a telescoping quadratic potential whose total is fixed by the leaf profile. One way to see this invariant is to complete every leaf to depth H H H t t t z z z 2 H − t 2^{H-t} 2 H − t H H H 2 H − t ( z 2 + ( H − t ) z ) 2^{H-t}(z^2+(H-t)z) 2 H − t ( z 2 + ( H − t ) z ) H − t H-t H − t
Proof. Put p t ( z ) = 2 H − t ( z 2 + ( H − t ) z ) p_t(z)=2^{H-t}(z^2+(H-t)z) p t ( z ) = 2 H − t ( z 2 + ( H − t ) z ) t < H t<H t < H z z z p t p_t p t
p t + 1 ( z ) + p t + 1 ( z + 1 ) − p t ( z ) = 2 H − t − 1 ( H − t ) . p_{t+1}(z)+p_{t+1}(z+1)-p_t(z)=2^{H-t-1}(H-t). p t + 1 ( z ) + p t + 1 ( z + 1 ) − p t ( z ) = 2 H − t − 1 ( H − t ) . Since p 0 ( 0 ) = 0 p_0(0)=0 p 0 ( 0 ) = 0 I t I_t I t t t t
∑ t , k p t ( z t , k ) = S ∗ : = ∑ t = 0 H − 1 I t 2 H − t − 1 ( H − t ) . \sum_{t,k}p_t(z_{t,k})=S_*:=\sum_{t=0}^{H-1}I_t2^{H-t-1}(H-t). t , k ∑ p t ( z t , k ) = S ∗ := t = 0 ∑ H − 1 I t 2 H − t − 1 ( H − t ) . Expanding the right-hand side of (19) and substituting this identity gives the required coefficients and constant:
g t , k = − 2 H − t ( ℓ t , k + r t , k + H − t ) , Q 0 = − S ∗ − ∑ t , k 2 H − t ℓ t , k r t , k . g_{t,k}=-2^{H-t}(\ell_{t,k}+r_{t,k}+H-t), \qquad Q_0=-S_*-\sum_{t,k}2^{H-t}\ell_{t,k}r_{t,k}. g t , k = − 2 H − t ( ℓ t , k + r t , k + H − t ) , Q 0 = − S ∗ − t , k ∑ 2 H − t ℓ t , k r t , k . The sorted endpoints make ( g t , k ) k (g_{t,k})_k ( g t , k ) k (19) is a nonnegative integer, and it vanishes exactly when its leaf coordinate belongs to the prescribed interval.
A small interval example. Use the two three-leaf trees from § 4 : T A T_A T A T B T_B T B n 1 = 1 , n 2 = 2 n_1=1,n_2=2 n 1 = 1 , n 2 = 2 I 0 = I 1 = 1 I_0=I_1=1 I 0 = I 1 = 1 S ∗ = 4 + 1 = 5 S_* = 4+1=5 S ∗ = 4 + 1 = 5 T A T_A T A
Table 14.
Then Q 0 = − 5 − ( 0 + 1 + 4 ) = − 10 Q_0=-5-(0+1+4)=-10 Q 0 = − 5 − ( 0 + 1 + 4 ) = − 10
Q ( T A ) = − 10 , Q ( T B ) = − 6 , Q ( T B ) − Q 0 = 2 ( 1 − 0 ) 2 + ( 0 − 1 ) 2 + ( 1 − 2 ) 2 = 4. Q(T_A)=-10,\qquad Q(T_B)=-6,\qquad Q(T_B)-Q_0=2(1-0)^2+(0-1)^2+(1-2)^2=4. Q ( T A ) = − 10 , Q ( T B ) = − 6 , Q ( T B ) − Q 0 = 2 ( 1 − 0 ) 2 + ( 0 − 1 ) 2 + ( 1 − 2 ) 2 = 4. The second tree remains a feasible candidate for the prescribed leaf profile; the linear score penalizes its interval violations. If instead the intervals are [ 0 , 1 ] [0,1] [ 0 , 1 ] [ 0 , 1 ] [0,1] [ 0 , 1 ] [ 1 , 2 ] [1,2] [ 1 , 2 ] ( − 4 , − 1 , − 3 ) (-4,-1,-3) ( − 4 , − 1 , − 3 ) Q = Q 0 = − 7 Q=Q_0=-7 Q = Q 0 = − 7
The score Q Q Q
Representing bits
The reduction represents a bit b ∈ { 0 , 1 } b\in\{0,1\} b ∈ { 0 , 1 } r + b r+b r + b r r r base . Copies of the same bit may have different bases. An internal vertex at a known coordinate can therefore be regarded as a known zero. All bases and subsequent changes to them are fixed before the values of the bits are chosen.
We give three constructions that copy a bit, test an edge constraint, and exchange a known zero with a stored bit. Each construction specifies the number of leaves at each level, intervals for their sorted coordinates, and coefficients in the leaf score. The optimization is over all coordinate multisets consistent with these data, including all possible final internal coordinates. This is essential for composition: an incorrect output could change every later operation, so it must incur a gap even if it no longer represents a bit at the prescribed base. For permitted inputs, the intended score is independent of the bits; the operations themselves must not introduce preferences among the graph choices. We describe the constructions relative to a common base; a translation of all coordinates and interval endpoints will make every coordinate nonnegative. The scores of these three constructions are invariant under this translation.
Copying
At any fixed depth, a complete binary subtree has unique vertices of minimum and maximum coordinate, reached by its leftmost and rightmost paths. The score on the following level is the difference between two leaf coordinates, so minimizing it favors the largest possible separation. This forces the extreme choices and leaves two copies of the input bit at fixed, separated bases.
Lemma A.2. For each b ∈ { 0 , 1 } b \in\{0,1\} b ∈ { 0 , 1 }
{ b } ⟶ { 1 + b , 5 + b } . \{b\} \longrightarrow\{1+b,5+b\}. { b } ⟶ { 1 + b , 5 + b } . Its score is − 6 -6 − 6 − 5 -5 − 5
Proof. Expand every internal vertex during the first four levels and create no leaves. At the fifth level, retain two of the 32 children and give coefficient zero to the other 30. At the sixth level, again retain two children, and assign coefficients ( 1 , − 1 ) (1,-1) ( 1 , − 1 )
Write p ≤ q p \le q p ≤ q b ≤ p ≤ q ≤ b + 5 b \le p \le q \le b+5 b ≤ p ≤ q ≤ b + 5 p , p + 1 , q , q + 1 p,p+1,q,q+1 p , p + 1 , q , q + 1 p − q − 1 ≥ − 6 p-q-1 \ge-6 p − q − 1 ≥ − 6 − 6 -6 − 6 p = b p=b p = b q = b + 5 q=b+5 q = b + 5 b b b b + 6 b+6 b + 6 1 + b 1+b 1 + b 5 + b 5+b 5 + b − 6 -6 − 6
At level five, prescribe the intervals
[ 1 , 2 ] , … , [ 1 , 2 ] , [ 2 , 3 ] , … , [ 2 , 3 ] , [ 3 , 4 ] , … , [ 3 , 4 ] , [ 4 , 5 ] , … , [ 4 , 5 ] . [1,2],\ldots,[1,2],\qquad[2,3],\ldots,[2,3],\qquad[3,4],\ldots,[3,4],\qquad[4,5],\ldots,[4,5]. [ 1 , 2 ] , … , [ 1 , 2 ] , [ 2 , 3 ] , … , [ 2 , 3 ] , [ 3 , 4 ] , … , [ 3 , 4 ] , [ 4 , 5 ] , … , [ 4 , 5 ] . The coordinate multiplicities at that level are 1, 5, 10, 10, 5, 1; after retaining the two extremes, these intervals contain the sorted leaf coordinates for either value of b b b [ 0 , 1 ] [0,1] [ 0 , 1 ] [ 6 , 7 ] [6,7] [ 6 , 7 ] − 1 -1 − 1
Edge constraints
The next construction consumes two stored bits and permits exactly the three pairs that can occur at the ends of an edge in an independent set. Its leaf coefficients are all zero; the constraint is imposed by the coordinate of one leaf.
Lemma A.3. For a , b ∈ { 0 , 1 } a,b \in\{0,1\} a , b ∈ { 0 , 1 } { − 3 + a , b } \{-3+a,b\} { − 3 + a , b } ( a , b ) ≠ ( 1 , 1 ) (a,b) \ne(1,1) ( a , b ) = ( 1 , 1 )
Proof. The first two levels each create two leaves and retain two internal vertices; the third level makes all four children leaves. Prescribe the following intervals, with coefficient zero on every leaf:
Table 1 (PDF p. 41).
Since the final leaves lie between − 1 -1 − 1 − 1 -1 − 1 − 2 -2 − 2
These ranges force the first-level leaves to be − 3 + a , b + 1 -3+a,b+1 − 3 + a , b + 1 { − 2 + a , b } \{-2+a,b\} { − 2 + a , b } − 2 + a , b + 1 -2+a,b+1 − 2 + a , b + 1 { − 1 + a , b } \{-1+a,b\} { − 1 + a , b }
these levels a child outside the internal-coordinate range must be a leaf, and a child outside the two leaf intervals must remain internal; applying these restrictions to a , b ∈ { 0 , 1 } a,b \in\{0,1\} a , b ∈ { 0 , 1 }
( − 1 + a , a b , max ( a , b ) , 1 + b ) . (-1+a,\ ab,\ \max(a,b),\ 1+b). ( − 1 + a , ab , max ( a , b ) , 1 + b ) . The second leaf belongs to { 0 } \{0\} { 0 } a b = 0 ab=0 ab = 0
Exchange with a known coordinate
The planar schedule will introduce each new graph-vertex choice at a specified position among the stored bits. To reach this position, it moves an internal vertex of known coordinate past successive stored bits. The following construction performs one such exchange while preserving the bit.
Lemma A.4. For each b ∈ { 0 , 1 } b \in\{0,1\} b ∈ { 0 , 1 }
{ − 1 , b } ⟶ { b , 4 } . \{-1,b\} \longrightarrow\{b,4\}. { − 1 , b } ⟶ { b , 4 } . Its score is zero. Every other complete sequence satisfying the prescribed leaf counts and intervals has score at least one, with no restriction on its final internal coordinates.
Proof. At each level, create two leaves and retain two internal vertices. Use the intervals and coefficients in Table 6 . The sequence
Table 6. Leaf data for exchanging a known coordinate with a stored bit.
{ − 1 , b } ⟶ { 0 , b } ⟶ { b , 1 } ⟶ { b , 2 } ⟶ { b , 3 } ⟶ { b , 4 } \{-1,b\} \longrightarrow\{0,b\} \longrightarrow\{b,1\} \longrightarrow\{b,2\} \longrightarrow\{b,3\} \longrightarrow\{b,4\} { − 1 , b } ⟶ { 0 , b } ⟶ { b , 1 } ⟶ { b , 2 } ⟶ { b , 3 } ⟶ { b , 4 } satisfies every interval. The only leaves with nonzero coefficients are the second leaf at level one and the first leaves at levels four and five. All three have coordinate b + 1 b+1 b + 1 2 , − 1 , − 1 2,-1,-1 2 , − 1 , − 1
To enumerate the other sequences, form the child multiset at each level and remove every leaf pair allowed by the corresponding row of Table 6 . For b = 0 b=0 b = 0 { 0 , 0 } \{0,0\} { 0 , 0 } { 0 , 1 } \{0,1\} { 0 , 1 } { 1 , 1 } \{1,1\} { 1 , 1 } { 1 , 2 } \{1,2\} { 1 , 2 } { 0 , 2 } \{0,2\} { 0 , 2 } { 0 , 1 } \{0,1\} { 0 , 1 } b = 1 b=1 b = 1 { 0 , 1 } \{0,1\} { 0 , 1 } { 0 , 2 } \{0,2\} { 0 , 2 } { 0 , 1 } \{0,1\} { 0 , 1 } { 1 , 1 } \{1,1\} { 1 , 1 } { 1 , 2 } \{1,2\} { 1 , 2 } { 2 , 3 } \{2,3\} { 2 , 3 } { 2 , 3 , 3 , 4 } \{2,3,3,4\} { 2 , 3 , 3 , 4 } [ 1 , 2 ] [1,2] [ 1 , 2 ] b = 1 b=1 b = 1 { 0 , 1 } \{0,1\} { 0 , 1 } { 1 , 1 } \{1,1\} { 1 , 1 } Table 7 , which records all sequences surviving four levels and every permitted fifth-level continuation.
Table 7. Internal coordinate multisets in the exchange construction, written as sorted pairs. A dash indicates that the sequence has no feasible continuation.
There is one complete sequence for b = 0 b=0 b = 0 b = 1 b=1 b = 1 2 − 1 − 1 = 0 2-1-1=0 2 − 1 − 1 = 0
Auxiliary operations
Waiting and moving. The constructions above act on one or two stored bits. During an operation, the other internal vertices must retain their coordinates, and before the next operation some bases must increase to place its inputs appropriately. For a single internal vertex at coordinate z z z z z z z + 1 z+1 z + 1 z + 1 z+1 z + 1 z z z waiting and moving , respectively. Intervals admitting both bit values can also permit a late unintended move. The scores below make such moves strictly more expensive while giving the same minimum for either stored bit.
Lemma A.5. The following operations have unique minimum-score sequences, with a gap of at least one to every other complete sequence satisfying their leaf data.
For every d ≥ 3 d \ge3 d ≥ 3 d d d r + b r+b r + b [ r + 1 , r + 2 ] [r+1,r+2] [ r + 1 , r + 2 ] d − 1 d-1 d − 1 − 1 , … , − 1 -1,\ldots,-1 − 1 , … , − 1
A three-level operation moves the bit from r + b r+b r + b r + 1 + b r+1+b r + 1 + b − 1 -1 − 1 [ r + 1 , r + 2 ] [r+1,r+2] [ r + 1 , r + 2 ] [ r + 1 , r + 2 ] [r+1,r+2] [ r + 1 , r + 2 ] [ r , r + 1 ] [r,r+1] [ r , r + 1 ] − 1 -1 − 1 0 0 0 1 1 1
Proof. For the first operation, waiting at every level gives leaf coordinate r + b + 1 r+b+1 r + b + 1 b = 0 b=0 b = 0 r r r b = 1 b=1 b = 1 r + 1 r+1 r + 1 r + 2 r+2 r + 2 r + 2 r+2 r + 2 r + 3 r+3 r + 3 d ≥ 3 d \ge3 d ≥ 3
For the second operation, the intended sequence waits twice and then moves. Its score is − ( r + b + 1 ) + ( r + b ) = − 1 -(r+b+1)+(r+b)=-1 − ( r + b + 1 ) + ( r + b ) = − 1 b = 0 b=0 b = 0 r r r b = 1 b=1 b = 1 r + 2 r+2 r + 2 [ r , r + 1 ] [r,r+1] [ r , r + 1 ] b = 1 b=1 b = 1 b = 0 b=0 b = 0 − 1 -1 − 1
A waiting example. Consider a three-level wait with base 10 and bit 1, so the input coordinate is 11. The three leaf intervals are all [ 11 , 12 ] [11,12] [ 11 , 12 ] ( 2 , − 1 , − 1 ) (2,-1,-1) ( 2 , − 1 , − 1 )
All three sequences satisfy every leaf interval. The last two illustrate the unit penalty for an incorrect output: the output coordinate is a conclusion of score minimization, not an additional constraint.
For a vertex of known coordinate, waiting and moving can instead be forced by exact leaf coordinates, with every coefficient zero. In particular, moving a known coordinate r r r r + 1 , r + 1 , r r+1,r+1,r r + 1 , r + 1 , r § 3.1.3 .
Choosing and terminating bits. We separate the reward for an original graph-vertex choice from the other score contributions, which we call the enforcing score . To choose a bit at a known coordinate r r r r + 1 r+1 r + 1 [ r , r + 1 ] [r,r+1] [ r , r + 1 ] r + b r+b r + b r + 1 − b r+1-b r + 1 − b b v b_v b v r + 1 − b v r+1-b_v r + 1 − b v § 3.1.3 .
To terminate a stored bit at r + b r+b r + b [ r + 1 , r + 2 ] [r+1,r+2] [ r + 1 , r + 2 ] [ r , r + 1 ] [r,r+1] [ r , r + 1 ] [ r + 1 , r + 2 ] [r+1,r+2] [ r + 1 , r + 2 ] b = 0 b=0 b = 0 b = 1 b=1 b = 1 r + 2 r+2 r + 2 § 3.1.3 .
Blocks. We call one of these operations, together with the prescribed waiting of all other internal vertices, a block . Every block has between three and six levels. Its enforcing score is the sum of the local enforcing scores. In an intended sequence, the outside waits contribute zero, so the block has the selected operation’s enforcing score. This value is independent of the stored bits and of the choice made in a graph-choice block. § 3.1.4 gives the leaf and nonleaf counts after the outside waits are included.
Block separation
Proof of Lemma 3.1 . Every descendant of a vertex at coordinate z z z [ z , z + 6 ] [z,z+6] [ z , z + 6 ]
Placement and preparation use three-level translation blocks. For neighboring bases r r r r + g r+g r + g g ≥ 5 g \ge5 g ≥ 5 r + 1 + 3 = r + 4 r+1+3=r+4 r + 1 + 3 = r + 4 r + g r+g r + g r + 3 r+3 r + 3 g = 4 g=4 g = 4 Table 8 .
Table 8. Separation cases for neighboring groups or entries. The active pair in an edge check or zero exchange is treated as one group.
Base gap four. First consider the outputs of a copy or a zero exchange, whose bases differ by four. Translate the notation so that the bases are zero and four. During the first two levels of a three-level translation, lower descendants are at most three and upper descendants are at least four. Lower waiting leaves belong to [ 1 , 2 ] [1,2] [ 1 , 2 ] [ 5 , 6 ] [5,6] [ 5 , 6 ] [ 1 , 2 ] [1,2] [ 1 , 2 ] p p p p , p + 1 p,p+1 p , p + 1 p ≤ 2 p \le2 p ≤ 2 [ 4 , 5 ] [4,5] [ 4 , 5 ] [ 5 , 6 ] [5,6] [ 5 , 6 ]
Base gaps three and two. In preparing a zero exchange, only a known coordinate moves past base gap three. Translate the lower known coordinate to zero and write the upper input as g + b g+b g + b g ∈ { 2 , 3 } g \in\{2,3\} g ∈ { 2 , 3 } 1 , 1 , 0 1,1,0 1 , 1 , 0 g ≥ 2 g \ge2 g ≥ 2 0 , 0 , 1 0,0,1 0 , 0 , 1 g + 1 g+1 g + 1
These cases exhaust the schedule. In each case, the leaf counts within a group also determine its number of remaining vertices at each level. The local constructions of Appendix § 8 consequently apply to each group. Each group’s score has a nonnegative integer excess over its intended value, with equality exactly for an intended coordinate sequence. These excesses add, so any unintended block has excess at least one.
Supplementary details for the first reduction
We supply the construction bounds and supporting details for § 3.2 , § 3.3 and § 3.4 . The schedule, instruction tables, placement rule, coefficients, and threshold are fixed in § 3.1 . We verify the realization and reference score, the shared priority estimate, and the block guarantee and recovery procedure. The interval and local-operation lemmas used here are proved in Appendix § 8 . Throughout, G = ( V , E ) G=(V,E) G = ( V , E ) n = ∣ V ∣ n=|V| n = ∣ V ∣ m = ∣ E ∣ m=|E| m = ∣ E ∣
Schedule correctness and operation count
For the fixed program in § 3.1.2 , an intended sequence uses the prescribed coordinate-multiset transitions; the original graph-vertex choices remain free.
Lemma B.1. The complete intended sequences satisfying the leaf intervals correspond exactly to the independent sets of G G G n m + 3 n + 3 m + 1 nm+3n+3m+1 nm + 3 n + 3 m + 1 O ( n + m ) O(n+m) O ( n + m )
Proof. The copy for an active edge stores the bit chosen at its lower endpoint. Copying and zero exchange preserve this bit, so the edge gadget at the upper endpoint receives the choices of the two endpoints. By Lemma A.3 , its intervals are feasible exactly when those choices are not both one. Thus every complete intended sequence selects an independent set. Conversely, the bits of any independent set permit all edge checks, and the other operations admit either input bit, giving a complete intended sequence.
Each of the n n n m m m n m nm nm n n n 2 m 2m 2 m n n n m m m n n n m m m
Placement correctness and size bounds
We analyze the placement rule of § 3.1.4 , with the same P = 4 ( n + m ) + 64 P=4(n+m)+64 P = 4 ( n + m ) + 64 Lemma B.1 , this bounds the number of internal vertices at any level, including the 16 temporary vertices used by copying.
During the right-to-left placement, the records already moved have consecutive base gaps 256. A moving record stays at least 256 below its already placed successor, if one exists, because its target is 256 below that successor’s target; its gap from an unmoved predecessor increases. Pairs not yet moved retain their old gaps, which are at least four, so no records cross. The gap-four pairs are outputs of copying or exchange; at such a gap, either both entries wait or only the upper entry moves, as handled explicitly in Lemma 3.1 .
The proof of Lemma 3.1 in Appendix § 8 .7 covers every base gap produced by these moves.
A completed placement has span at most 256 P 256P 256 P O ( P ) O(P) O ( P ) O ( P ) O(P) O ( P ) O ( P 2 ) O(P^2) O ( P 2 ) Lemma B.1 , there are O ( n m + n + m ) O(nm+n+m) O ( nm + n + m ) m = O ( n ) m=O(n) m = O ( n )
H = O ( n 4 ) , N = O ( n 5 ) . H=O(n^4), \qquad N=O(n^5). H = O ( n 4 ) , N = O ( n 5 ) . The bound on N N N 2 P 2P 2 P Lemma A.1 applies.
Coefficient order and encoding length
We verify the output specified in § 3.1.5 .
Ordering the final coefficient rows. We must verify u t , 1 ≥ ⋯ ≥ u t , n t u_{t,1} \ge\cdots\ge u_{t,n_t} u t , 1 ≥ ⋯ ≥ u t , n t k , k + 1 k,k+1 k , k + 1 t t t i = i ( t ) i=i(t) i = i ( t )
If the two intervals are distinct, their endpoint sums differ by at least one. Equation (2) gives g t , k − g t , k + 1 ≥ 1 g_{t,k}-g_{t,k+1} \ge1 g t , k − g t , k + 1 ≥ 1 2 A ∗ 2A_\ast 2 A ∗
u t , k − u t , k + 1 ≥ B J + 1 − 2 A ∗ B J − i + 1 − 1 ≥ B J + 1 − 2 A ∗ B J − 1 = B J ( B − 2 A ∗ ) − 1 > 0 , \begin{aligned}
u_{t,k}-u_{t,k+1} &\ge B^{J+1}-2A_\ast B^{J-i+1}-1 \\
&\ge B^{J+1}-2A_\ast B^J-1 \\
&=B^J(B-2A_\ast)-1>0,
\end{aligned} u t , k − u t , k + 1 ≥ B J + 1 − 2 A ∗ B J − i + 1 − 1 ≥ B J + 1 − 2 A ∗ B J − 1 = B J ( B − 2 A ∗ ) − 1 > 0 , since H ≥ 1 H \ge1 H ≥ 1 B = 2 H A ∗ + 2 ≥ 2 A ∗ + 2 B=2HA_\ast+2 \ge2A_\ast+2 B = 2 H A ∗ + 2 ≥ 2 A ∗ + 2
If the intervals are identical, the placement and instruction templates must also be used. § 3.1.4 separates the interval lists of different groups, including outside waits. Within a selected instruction row, the repetitions occur at level five of Copy or Split; their entries all have e = δ = 0 e=\delta=0 e = δ = 0 § 3.1.3 . Hence equal intervals in the generated row give equal final coefficients. The two cases prove that every output row is nonincreasing. This conclusion uses the generated templates, not merely the interval widths.
Binary encoding length and running time. Let n = ∣ V ( G ) ∣ n=|V(G)| n = ∣ V ( G ) ∣ m = ∣ E ( G ) ∣ m=|E(G)| m = ∣ E ( G ) ∣ P = 4 ( n + m ) + 64 P=4(n+m)+64 P = 4 ( n + m ) + 64 § 2 gives
H = O ( n 4 ) , N = O ( n 5 ) , J ≤ H . H=O(n^4), \qquad N=O(n^5), \qquad J\le H. H = O ( n 4 ) , N = O ( n 5 ) , J ≤ H . A block has at most six levels, O ( P ) O(P) O ( P ) E i = O ( P ) E_i=O(P) E i = O ( P ) A ∗ = O ( P ) A_\ast=O(P) A ∗ = O ( P ) B = 2 H A ∗ + 2 B=2HA_\ast+2 B = 2 H A ∗ + 2 n n n O ( H ) O(H) O ( H ) g t , k g_{t,k} g t , k O ( H + log ( H + 1 ) ) O(H+\log(H+1)) O ( H + log ( H + 1 )) B J + 1 B^{J+1} B J + 1 O ( ( J + 1 ) log B ) O((J+1)\log B) O (( J + 1 ) log B ) O ( H + J log B + log ( H + 1 ) + log ( A ∗ + 1 ) ) O(H+J\log B+\log(H+1)+\log(A_\ast+1)) O ( H + J log B + log ( H + 1 ) + log ( A ∗ + 1 ))
The two scans specified in § 3.1.5 use O ( N + H + J ) O(N+H+J) O ( N + H + J ) (4) and (5) .
Tree realization and the reference score
We justify the realization and score assertions of § 3.2 . Fix an independent set S S S
Completing and realizing the coordinate sequence. The interfaces in § 3.1.3 preserve each stored bit and update its base as prescribed; a known record remains known until its original choice. At an edge check, the active-edge invariant of Lemma B.1 supplies the two endpoint bits. Independence makes this a permitted input to Lemma A.3 . Every other selected operation admits its prescribed continuation, and the schedule terminates all records, including the reserve.
The selected constructions have the same leaf and internal counts for all permitted inputs, and each outside wait contributes one leaf and one continuing vertex at each level. The placement and assembly rules of § 3.1.4 give the prescribed counts and the fixed order in which local leaf lists are merged, so their intended coordinates satisfy the intervals at their global sorted ranks. Consequently the resulting multisets satisfy
X 0 = { 0 } , X t ⊆ E ( X t − 1 ) ( 1 ≤ t ≤ H ) , X H = ∅ . X_0 = \{0\}, \qquad X_t \subseteq\mathcal{E}(X_{t-1}) \quad(1 \le t \le H), \qquad X_H = \varnothing. X 0 = { 0 } , X t ⊆ E ( X t − 1 ) ( 1 ≤ t ≤ H ) , X H = ∅ . To obtain a concrete tree, expand every current internal vertex into its two children, retain occurrences with the coordinates specified by X t X_t X t x x x x x x x + 1 x+1 x + 1
The constants in the final score. The empty independent set gives an interval-respecting realization, so the joint realizability hypothesis of Lemma A.1 holds. That lemma identifies the constructed constant (4) as the common value Q ( T S ) = Q 0 Q(T_S) = Q_0 Q ( T S ) = Q 0 S S S
For each block, let s i s_i s i Table 4 . The local bounds in Appendix § 8 show that this value is independent of the input bits. Every outside wait has score zero, so the entire block has f i ( T S ) = s i f_i(T_S) = s_i f i ( T S ) = s i
Only original choices have reward markers. If ρ v \rho_v ρ v v v v ρ v + 1 − b v \rho_v + 1 - b_v ρ v + 1 − b v
f 0 ( T S ) = ∑ v ∈ V ( ρ v + 1 − b v ) = ∑ v ∈ V ( ρ v + 1 ) − ∣ S ∣ . f_0(T_S) = \sum_{v \in V}(\rho_v + 1 - b_v) = \sum_{v \in V}(\rho_v + 1) - |S|. f 0 ( T S ) = v ∈ V ∑ ( ρ v + 1 − b v ) = v ∈ V ∑ ( ρ v + 1 ) − ∣ S ∣. Substituting these component values into (10) and using (5) gives (6) . Taking S = ∅ S = \varnothing S = ∅ C C C
Polynomial-time construction of the realization. The schedule, working table, and coefficient encodings have polynomial size by Appendices B.§ 2 and B.§ 3 . Substituting the bits, forming the multisets, and selecting their child occurrences take polynomial time. The realized full tree has 2 N − 1 2N - 1 2 N − 1 C C C
A shared priority comparison
The comparisons in § 3.3.1 and § 3.3.2 use the same estimate. We prove it once for the components of (10) . The interval identity used in the first comparison is proved separately in Lemma A.1 .
The sum of absolute coefficients of f i f_i f i E i < A ∗ E_i < A_\ast E i < A ∗ i ≥ 1 i \ge1 i ≥ 1 f 0 f_0 f 0 n < A ∗ n < A_\ast n < A ∗ [ 0 , H ] [0,H] [ 0 , H ] T T T
∣ f i ( T ) ∣ ≤ H A ∗ , ∣ f i ( T ) − f i ( T 0 ) ∣ ≤ D : = 2 H A ∗ ( 0 ≤ i ≤ J ) . \lvert f_i(T) \rvert\le H A_\ast, \qquad\lvert f_i(T) - f_i(T_0) \rvert\le D := 2H A_\ast\quad(0 \le i \le J). ∣ f i ( T )∣ ≤ H A ∗ , ∣ f i ( T ) − f i ( T 0 )∣ ≤ D := 2 H A ∗ ( 0 ≤ i ≤ J ) . This estimate permits signed coefficients, interval violations, and incorrect internal-coordinate sequences.
Suppose a component with multiplier B q B^q B q 1 ≤ q ≤ J + 1 1 \le q \le J + 1 1 ≤ q ≤ J + 1 T 0 T_0 T 0 T 0 T_0 T 0 B q − 1 , … , B , 1 B^{q-1},\ldots,B,1 B q − 1 , … , B , 1 f 0 , … , f J f_0,\ldots,f_J f 0 , … , f J (10) gives
score ( T ) − C ≥ B q − D ∑ a = 0 q − 1 B a = B q − D B q − 1 B − 1 > 0 , (20) \operatorname{score}(T)-C \ge B^q-D\sum_{a=0}^{q-1}B^a=B^q-D\frac{B^q-1}{B-1}>0, \tag*{(20)} score ( T ) − C ≥ B q − D a = 0 ∑ q − 1 B a = B q − D B − 1 B q − 1 > 0 , (20) because B = D + 2 B=D+2 B = D + 2 D < B − 1 D<B-1 D < B − 1 q = J + 1 q=J+1 q = J + 1 q = J − i + 1 q=J-i+1 q = J − i + 1 i i i f 0 f_0 f 0
A numerical comparison. For the first-error comparison after interval compliance, suppose J = 4 J=4 J = 4 D = 200 D=200 D = 200 B = 202 B=202 B = 202 q = 2 q=2 q = 2
Table 15.
These are illustrative values, rather than the multipliers of the running graph. At the final block, q = 1 q=1 q = 1 B B B D = B − 2 D=B-2 D = B − 2 C C C
Block compatibility and recovery
We supply the block-composition and realization details used in § 3.3.2 . Let T T T score ( T ) ≤ C \operatorname{score}(T)\le C score ( T ) ≤ C § 3.3.1 , its sorted leaf coordinates satisfy every prescribed interval. We use the candidate bits and component scores defined in the main argument.
Shared boundary states and disjoint leaf rows. The fixed block lengths determine which fragment of T T T
Table 16.
These lengths illustrate the indexing, rather than the initial instructions of the running graph. The internal vertices at depth six form the whole input frontier of block two: its selected records participate in the operation, and the others wait. The second block creates no leaf entries at depth six. Thus adjacent blocks share a boundary state but no leaf position. Empty leaf rows still count toward a block’s length.
The block guarantee and its hypotheses. Fix a scheduled block with its prescribed input coordinate list, for some stored bit values. Consider every complete child selection satisfying the block’s global leaf counts and sorted leaf intervals. Leaf origins and final internal coordinates are unrestricted. Lemma 3.1 , proved in Appendix § 8 .7, decomposes every such selection into the selected operation and the outside waits, with each group satisfying its local counts and intervals. This is the step that permits the local score bounds to be applied inside the global sorted rows.
The bounds in Lemmas A.2 , A.3 , A.4 and A.5 , together with the supporting operations in Appendix § 8 .6, apply to these complete local sequences even when their final coordinates are arbitrary. A check receiving 11 has no permitted completion. Otherwise, write F g F_g F g g g g c g c_g c g
f i ( T ) − s i = ∑ g ( F g − c g ) ≥ 0. f_i(T) - s_i = \sum_g (F_g - c_g) \ge0. f i ( T ) − s i = g ∑ ( F g − c g ) ≥ 0. Equality requires every group to follow its intended coordinate sequence; an incorrect complete block therefore has f i ( T ) ≥ s i + 1 f_i(T) \ge s_i + 1 f i ( T ) ≥ s i + 1 − 6 -6 − 6 § 8 .6 illustrates the gap while allowing arbitrary final internal coordinates.
Either outcome of an original Choose is intended. In its equality case, the last children are ρ v , ρ v + 1 \rho_v, \rho_v + 1 ρ v , ρ v + 1 ρ v + 1 − b v \rho_v + 1 - b_v ρ v + 1 − b v ρ v + b v \rho_v + b_v ρ v + b v
At the first incorrect block, the correct prefix supplies precisely the input list required by Lemma 3.1 . The stored bits need not agree with those of the all-zero reference tree, and no assumption is made that the prefix extends to an independent set. Their intended enforcing values nevertheless agree. This verifies the hypotheses used in (11) : the total interval score and all earlier enforcing scores agree with the reference, while every original-choice reward remains in the lowest-priority component. The general comparison (20) bounds all later scores without assuming separation or correctness after this block.
Replaying a concrete ordered tree. The main argument proves that the recovered assignment reproduces the successive multisets X t ( T ) X_t(T) X t ( T ) L t ( T ) L_t(T) L t ( T ) t − 1 t - 1 t − 1 T T T t t t X t ( T ) X_t(T) X t ( T ) T T T
Polynomial-time recovery. Traverse T T T G G G § 3.3.2 then identifies the vertices of S T S_T S T N N N 2 N − 1 2N - 1 2 N − 1 § 2 and B.3. Traversal, sorting, and exact score evaluation therefore have polynomial bit complexity.
