[Model] RegisterSufficiency

[isPANN]

Motivation

REGISTER SUFFICIENCY (P293) from Garey & Johnson, A11 PO1. A fundamental NP-complete problem in compiler optimization: given a directed acyclic graph representing a straight-line computation and a bound K, determine whether the computation can be performed using at most K registers. The DAG vertices represent values (inputs, intermediates, outputs), and edges represent data dependencies. The evaluation order determines which values must be held simultaneously in registers. NP-complete even when all vertices have out-degree ≤ 2 [Sethi, 1975]. The problem connects compiler register allocation to scheduling theory.

Associated rules:

• R225: 3SAT → Register Sufficiency (this model is the target)
• R137: Register Sufficiency → Sequencing to Minimize Maximum Cumulative Cost (this model is the source)

Definition

Name: RegisterSufficiency

Reference: Garey & Johnson, Computers and Intractability, A11 PO1

Mathematical definition:

INSTANCE: Directed acyclic graph G = (V, A), positive integer K.
QUESTION: Is there a computation for G that uses K or fewer registers, i.e., an ordering v_1, v_2, ..., v_n of the vertices in V, where n = |V|, and a sequence S_0, S_1, ..., S_n of subsets of V, each satisfying |S_i| ≤ K, such that S_0 is empty, S_n contains all vertices with in-degree 0 in G, and, for 1 ≤ i ≤ n, v_i ∈ S_i, S_i \ {v_i} ⊆ S_{i−1}, and S_{i−1} contains all vertices u for which (v_i, u) ∈ A?

Variables

• Count: n = |V| (one variable per vertex, representing its position in the evaluation order)
• Per-variable domain: {0, 1, ..., n−1} — the position of the vertex in the computation ordering
• Meaning: π(i) ∈ {0, ..., n−1} gives the evaluation position of vertex v_i. The ordering must be a valid computation: when evaluating v_i, all its successors (operands) must already be in registers (i.e., in the current register set S_{i−1}). The register set at each step must have size ≤ K. Vertices with in-degree 0 are "leaf" inputs that must persist in registers until consumed.

Schema (data type)

Type name: RegisterSufficiency
Variants: none (no type parameters; the DAG is unweighted)

Field	Type	Description
num_vertices	usize	Number of vertices n =
arcs	Vec<(usize, usize)>	Directed arcs (v, u) ∈ A (v depends on u)
bound	usize	Register bound K

Complexity

• Best known exact algorithm: The problem is NP-complete [Sethi, 1975]. It remains NP-complete even when all vertices have out-degree ≤ 2. For expression trees (DAGs with tree structure), the Sethi-Ullman algorithm solves the problem in O(n) time [Sethi & Ullman, 1970]. For general DAGs, Kessler's dynamic programming algorithm over register states has complexity O(n² · 2ⁿ) [Kessler, 1998]. The trivial brute-force approach enumerates all n! orderings in O(n! · n) time.
• declare_variants! complexity string: "num_vertices ^ 2 * 2 ^ num_vertices"

Extra Remark

Full book text:

INSTANCE: Directed acyclic graph G = (V,A), positive integer K.
QUESTION: Is there a computation for G that uses K or fewer registers, i.e., an ordering v1,v2,...,vn of the vertices in V, where n = |V|, and a sequence S0,S1,...,Sn of subsets of V, each satisfying |Si| ≤ K, such that S0 is empty, Sn contains all vertices with in-degree 0 in G, and, for 1 ≤ i ≤ n, vi ∈ Si, Si−{vi} ⊆ Si−1, and Si−1 contains all vertices u for which (vi,u) ∈ A?
Reference: [Sethi, 1975]. Transformation from 3SAT.
Comment: Remains NP-complete even if all vertices of G have out-degree 2 or less. The variant in which "recomputation" is allowed (i.e., we ask for sequences v1,v2,...,vm and S0,S1,...,Sm, where no a priori bound is placed on m and the vertex sequence can contain repeated vertices, but all other properties stated above must hold) is NP-hard and is not known to be in NP.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all n! evaluation orderings of the DAG; simulate register usage for each; check if max registers ≤ K.)
• It can be solved by reducing to integer programming. (Binary ILP: x_{ij} ∈ {0,1} = vertex i evaluated at step j; enforce dependency constraints; track register set sizes at each step; constrain all set sizes ≤ K.) See companion issue: [Rule] RegisterSufficiency to ILP #782
• Other: Sethi-Ullman algorithm for trees [Sethi & Ullman, 1970]; DP over register states for general DAGs [Kessler, 1998].

Example Instance

Input:
DAG G = (V, A):
V = {v_1, v_2, v_3, v_4, v_5, v_6, v_7}
Arcs (directed edges, "depends on"):

• (v_3, v_1): v_3 uses v_1 as input
• (v_3, v_2): v_3 uses v_2 as input
• (v_4, v_2): v_4 uses v_2 as input
• (v_5, v_3): v_5 uses v_3 as input
• (v_5, v_4): v_5 uses v_4 as input
• (v_6, v_1): v_6 uses v_1 as input
• (v_7, v_5): v_7 uses v_5 as input
• (v_7, v_6): v_7 uses v_6 as input

K = 3.

Vertices with in-degree 0 (inputs/leaves): v_1, v_2. These values must be loaded into registers when first consumed.
Vertex with in-degree 0 in the GJ sense (no outgoing arcs = final output): v_7.

Feasible computation order (leaves first):
Order: v_1, v_2, v_3, v_4, v_6, v_5, v_7

Register simulation:

• Load v_1: S = {v_1}, |S| = 1 ≤ 3 ✓
• Load v_2: S = {v_1, v_2}, |S| = 2 ≤ 3 ✓
• Compute v_3 (needs v_1, v_2): S = {v_1, v_2, v_3}, |S| = 3 ≤ 3 ✓. v_1 still needed by v_6, v_2 still needed by v_4.
• Compute v_4 (needs v_2): v_2 no longer needed after. S = {v_1, v_3, v_4}, |S| = 3 ≤ 3 ✓
• Compute v_6 (needs v_1): v_1 freed. S = {v_3, v_4, v_6}, |S| = 3 ≤ 3 ✓
• Compute v_5 (needs v_3, v_4): v_3, v_4 freed. S = {v_5, v_6}, |S| = 2 ≤ 3 ✓
• Compute v_7 (needs v_5, v_6): S = {v_7}, |S| = 1 ≤ 3 ✓

Maximum register usage = 3 ≤ K = 3 ✓

Answer: YES — a computation using at most 3 registers exists. The minimum number of registers for this DAG is exactly 3 (verified by exhaustive enumeration of all 21 valid topological orderings; no ordering achieves K = 2).

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem; planned reductions connecting it to 3SAT and scheduling problems
Non-trivial	✅ Pass	DAG register allocation is distinct from all existing models
Correctness	⚠️ Warn	Kessler 1998 complexity is O(n * 2^(2n)), not O(n * 2^n) as stated
Well-written	❌ Fail	Example contains visible trial-and-error; no concrete complexity string for declare_variants!

Overall: 2 passed, 1 warning, 1 failed

---

Usefulness

RegisterSufficiency does not exist in the codebase. It is a genuinely novel problem with planned connections to the reduction graph: an incoming reduction from 3SAT (R225) and an outgoing reduction to Sequencing to Minimize Maximum Cumulative Cost (R137). This would make it a well-connected node. The motivation clearly identifies compiler optimization as the application domain.

Non-trivial

This problem has a fundamentally different structure from all existing models. It involves a DAG with a vertex ordering and dynamic tracking of register sets — a scheduling/sequencing problem over computation graphs. This is not a variant of any existing graph, formula, set, or algebraic problem.

Correctness

References verified:

• Sethi (1975): Confirmed. "Complete Register Allocation Problems", SIAM Journal on Computing, 4(2):226-248, 1975. The NP-completeness result for register sufficiency on DAGs is correct, and the restriction to out-degree <= 2 remaining NP-complete is established.
• Kessler (1998): Confirmed as existing. "Scheduling expression DAGs for minimal register need", Computer Languages, 1998. However, the issue claims complexity "O(n * 2^n)" but the paper gives O(n * 2^(2n)) worst-case complexity. This is a factual inaccuracy — the exponent is 2n, not n.
• Garey & Johnson PO1: Consistent with the Program Optimization category numbering.
• Sethi-Ullman algorithm: Correctly described as solving the tree-structured case in O(n) time.

Well-written

Failures:

1. Example contains visible debugging. The example starts with a "root-to-leaves" evaluation order, then says "But wait — at step i we evaluate v_i and remove it. We need S_{i-1} to contain all successors" and "Let me use the correct semantics... Actually, the GJ definition evaluates from root to leaves (consuming values). Let's use a forward computation order (leaves first)." This trial-and-error should be cleaned up into a single clean worked example.

2. No concrete complexity string for declare_variants!. The complexity section discusses multiple algorithms but provides no expression in the format needed (e.g., "num_vertices! * num_vertices" for brute force, or "num_vertices * 2^(2 * num_vertices)" for Kessler's DP). This must be specified.

3. Kessler complexity error. The claim of O(n * 2^n) should be corrected to O(n * 2^(2n)).

Passes:

• All template sections are present and substantive
• The formal definition is faithfully reproduced from G&J and is mathematically well-formed
• Variables section correctly identifies the permutation encoding
• Schema is clean and simple with appropriate field types
• Both brute-force and ILP solver paths are identified with clear descriptions
• The final worked-through example (leaves-first order) is actually correct and demonstrates the problem well
• Symbol usage is consistent across sections

Recommendations

• Clean up the example: remove the false start and present only the correct leaves-first evaluation with register simulation
• Fix the Kessler complexity from O(n * 2^n) to O(n * 2^(2n))
• Add a concrete complexity string for declare_variants! — suggest: "num_vertices * 2^(2 * num_vertices)" based on Kessler's DP
• The "Extra Remark" section about the recomputation variant is a nice addition — consider noting this is a separate (harder) problem

[isPANN]

Issue Quality Check — Model (Re-check)

Check	Result	Details
Usefulness	✅ Pass	Novel problem; 2 planned reductions (R225, R137) connecting it to the graph
Non-trivial	✅ Pass	DAG register allocation is distinct from all existing models
Correctness	❌ Fail	Kessler 1998 complexity is O(n² · 2ⁿ), not O(n · 2ⁿ) as stated
Well-written	❌ Fail	Example has visible debugging; no declare_variants! complexity string; ILP crossref missing

Overall: 2 passed, 0 warnings, 2 failed

Re-check of previous report (2026-03-12). Changes: Correctness upgraded from ⚠️ Warn to ❌ Fail (the previous review's correction to O(n · 2^(2n)) was also wrong — verified correct bound is O(n² · 2ⁿ)). Well-written remains ❌ Fail.

---

Usefulness

RegisterSufficiency (G&J A11 PO1) does not exist in the codebase. Two planned reductions connect it to the existing graph:

• R225: 3SAT → RegisterSufficiency (incoming)
• R137: RegisterSufficiency → SequencingToMinimizeMaximumCumulativeCost (outgoing)

This makes it a well-connected node bridging logic and scheduling problems. The compiler optimization motivation is clear and concrete.

Non-trivial

This problem involves a DAG vertex ordering with dynamic register set tracking — a scheduling/sequencing problem over computation graphs. It has fundamentally different structure from all 112 existing models (graph, formula, set, algebraic, misc). Not a variant or repackaging of any existing problem.

Correctness

References verified:

Reference	Status	Details
Sethi (1975)	✅ Confirmed	"Complete Register Allocation Problems", SIAM J. Comput. 4(3):226-248. NP-completeness of register sufficiency on DAGs confirmed. Conference version at STOC 1973.
Kessler (1998)	❌ Wrong complexity	"Scheduling Expression DAGs for Minimal Register Need", Computer Languages 24(1):33-53. Actual complexity is O(n² · 2ⁿ), not O(n · 2ⁿ) as the issue claims. Note: the previous review's correction to O(n · 2^(2n)) was also incorrect — it misread the plain-text notation.
Sethi-Ullman (1970)	✅ Confirmed	"The Generation of Optimal Code for Arithmetic Expressions", JACM 17(4):715-728. O(n) time for tree-structured cases confirmed.
G&J PO1	✅ Confirmed	Consistent with Garey & Johnson Appendix A numbering.

Example validated by brute-force Python script:

• Enumerated all 5040 permutations of 7 vertices; 21 are valid topological orderings
• Minimum registers needed: 3 (K=2 is impossible) — the example is tight
• 15 of 21 valid orderings achieve K=3; the remaining 6 require K=4
• The specific ordering claimed (v₁, v₂, v₃, v₄, v₆, v₅, v₇) is valid and uses exactly 3 registers ✅
• Register trace confirmed: peak at S₃ = {v₁, v₂, v₃} with |S₃| = 3

Well-written

Failures:

1. Example contains visible debugging. The example starts with a root-to-leaves ordering, then says "But wait — at step i we evaluate v_i and remove it..." and "Let me use the correct semantics... Actually, the GJ definition evaluates from root to leaves..." This trial-and-error must be cleaned up into a single clean worked example. The final leaves-first trace is correct.

2. No concrete complexity string for declare_variants!. The Complexity section discusses multiple algorithms but provides no expression in the format needed for implementation (e.g., "num_vertices ^ 2 * 2 ^ num_vertices" for Kessler's DP). This must be specified.

3. Kessler complexity error. Must be corrected from O(n · 2ⁿ) to O(n² · 2ⁿ).

4. ILP solving claimed but no companion issue linked. The "How to solve" section checks the ILP box, but there is no [Rule] RegisterSufficiency to ILP companion issue linked in the body. Either uncheck ILP or file a companion rule issue and link it.

Passes:

• All template sections present and substantive
• Formal definition faithfully reproduced from G&J, mathematically well-formed
• Variables section correctly identifies the permutation encoding
• Schema is clean with appropriate field types (DAG arcs + bound)
• Brute-force solver path clearly described
• Symbol usage consistent across sections
• Example instance is non-trivial (7 vertices, 8 arcs) and tight (K=3 is the true minimum)
• Example has multiple suboptimal configurations (6 orderings need K=4)

Recommendations

• Clean up the example: remove the false start, present only the correct leaves-first evaluation with register simulation
• Fix Kessler complexity: O(n · 2ⁿ) → O(n² · 2ⁿ), and add a concrete declare_variants! string: "num_vertices ^ 2 * 2 ^ num_vertices"
• Either file a [Rule] RegisterSufficiency to ILP issue and link it, or uncheck the ILP box
• The "Extra Remark" about the recomputation variant is a nice touch — consider noting it's a separate (harder) problem not in NP

[isPANN]

Fix-issue changelog

• Fixed Kessler (1998) complexity from O(n · 2ⁿ) to O(n² · 2ⁿ)
• Added declare_variants! complexity string: "num_vertices ^ 2 * 2 ^ num_vertices"
• Cleaned up example: removed trial-and-error false start, kept only the correct leaves-first evaluation with register simulation
• Filed companion issue [Rule] RegisterSufficiency to ILP #782 ([Rule] RegisterSufficiency to ILP) and linked it in the "How to solve" section

Applied by /fix-issue.