[Model] MinimumRegisterSufficiencyForLoops

[isPANN]

Motivation

REGISTER SUFFICIENCY FOR LOOPS (P295) from Garey & Johnson, A11 PO3. Equivalent to circular arc graph coloring — a fundamental problem in compiler optimization and graph theory.

Associated rules:

• [Rule] Permutation Generation to MinimumRegisterSufficiencyForLoops #874: PermutationGeneration → MinimumRegisterSufficiencyForLoops (NP-completeness proof)

Structural connections:

• Equivalent to circular arc graph coloring: the chromatic number of the intersection graph of arcs on a circle
• Generalizes interval graph coloring (which is polynomial — chromatic number = clique number for interval graphs)
• Applications: loop register allocation in compilers, channel assignment in wireless networks

Definition

Name: MinimumRegisterSufficiencyForLoops
Reference: Garey & Johnson, Computers and Intractability, A11 PO3

Mathematical definition:

INSTANCE: Set V of loop variables, loop length N ∈ Z⁺, for each variable v ∈ V a start time s(v) ∈ Z₀⁺ and a duration l(v) ∈ Z⁺.
OBJECTIVE: Find an assignment f: V → Z⁺ that minimizes the number of registers used (i.e., |image(f)|), subject to the constraint that no two variables assigned to the same register have overlapping live ranges (considering wrap-around modulo N).

Two variables u, v conflict iff their circular arcs [s(u), s(u)+l(u)) mod N and [s(v), s(v)+l(v)) mod N overlap.

Variables

• Count: |V| (one variable per loop variable)
• Per-variable domain: {1, 2, ..., |V|}
• Meaning: f(v) = k means loop variable v is stored in register k. Minimize the number of distinct registers used while ensuring no two conflicting variables share a register.

Schema (data type)

Type name: MinimumRegisterSufficiencyForLoops
Variants: none

Field	Type	Description
loop_length	usize	The loop length N (circle circumference)
variables	Vec<(usize, usize)>	For each loop variable: (start_time, duration)

Notes:

• This is an optimization problem: Value = Min<usize>.
• Key getter methods: loop_length() (= N), num_variables() (= |V|).

Complexity

• Decision complexity: NP-complete (Garey, Johnson, Miller, Papadimitriou, 1980; transformation from Permutation Generation). Solvable in polynomial time for any fixed K.
• Best known exact algorithm: O*(K^|V|) brute force over all register assignments.
• Concrete complexity expression: "num_variables^num_variables" (for declare_variants!; K ≤ |V|)
• Relationship to clique number: For circular arc graphs, χ can exceed ω by at most 1 (Tucker, 1975).
• References:
  • M.R. Garey, D.S. Johnson, G.L. Miller, C.H. Papadimitriou (1980). "The Complexity of Coloring Circular Arcs and Chords." SIAM J. Algebraic and Discrete Methods 1(2), pp. 216-227.
  • A. Tucker (1975). "Coloring a Family of Circular Arcs." SIAM J. Applied Math 29(3), pp. 493-502.

Extra Remark

Full book text:

INSTANCE: Set V of loop variables, a loop length N ∈ Z+, for each variable v ∈ V a start time s(v) ∈ Z0+ and a duration l(v) ∈ Z+, and a positive integer K.
QUESTION: Can the loop variables be safely stored in K registers, i.e., is there an assignment f: V→{1,2,...,K} such that if f(v) = f(u) for some u ≠ v ∈ V, then s(u) ≤ s(v) implies s(u) + l(u) ≤ s(v) and s(v) + l(v)(mod N) ≤ s(u)?
Reference: [Garey, Johnson, Miller, and Papadimitriou, 1978]. Transformation from permutation generation.
Comment: Solvable in polynomial time for any fixed K.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all f: V → {1,...,|V|}; find minimum valid coloring.)
• It can be solved by reducing to integer programming. (Integer variable per loop variable; for each conflicting pair, add f(u) ≠ f(v) constraints; minimize number of distinct values. Companion rule issue to be filed separately.)
• Other: For fixed K, polynomial-time DP on circular arc intersection graph.

Example Instance

Input:
Loop length N = 6, 3 variables:

Variable	Start	Duration	Arc
v₁	0	3	[0, 3)
v₂	2	3	[2, 5)
v₃	4	3	[4, 1) wrap

Conflict pairs (overlapping arcs): v₁-v₂ (overlap [2,3)), v₂-v₃ (overlap [4,5)), v₃-v₁ (wrap: [4,1) ∩ [0,3) = [0,1)).

All three pairs conflict — this is a 3-clique. The minimum number of registers is 3.

Optimal assignment: f(v₁)=1, f(v₂)=2, f(v₃)=3. All conflicts resolved.
Optimal value: Min(3).

No 2-coloring exists because the conflict graph is K₃ (complete graph on 3 vertices requires 3 colors).

Python validation script

from itertools import product

N = 6
vars = [(0, 3), (2, 3), (4, 3)]  # (start, duration)

def arcs_overlap(s1, l1, s2, l2, N):
    # Check if circular arcs [s1, s1+l1) and [s2, s2+l2) mod N overlap
    for t in range(N):
        in1 = any((s1 + d) % N == t for d in range(l1))
        in2 = any((s2 + d) % N == t for d in range(l2))
        if in1 and in2:
            return True
    return False

# Build conflict pairs
conflicts = []
for i in range(3):
    for j in range(i+1, 3):
        if arcs_overlap(vars[i][0], vars[i][1], vars[j][0], vars[j][1], N):
            conflicts.append((i, j))

assert len(conflicts) == 3  # 3-clique
print(f"Conflicts: {conflicts} (3-clique)")

# Check minimum coloring
for K in range(1, 4):
    count = 0
    for assign in product(range(1, K+1), repeat=3):
        if all(assign[i] != assign[j] for i, j in conflicts):
            count += 1
    print(f"K={K}: {count} valid colorings")
    if count > 0:
        print(f"Minimum colors: {K}")
        break

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem, distinct from existing RegisterSufficiency (DAG-based, PO1)
Non-trivial	✅ Pass	Circular arc coloring has genuinely different constraints from existing problems
Correctness	❌ Fail	Example instance answer is wrong (K=3 suffices, not K=4)
Well-written	❌ Fail	Multiple issues: broken example, no concrete complexity expression, no linked ILP rule issue

Overall: 2 passed, 0 warnings, 2 failed

---

Usefulness

Pass. RegisterSufficiencyForLoops (G&J A11 PO3) is a distinct problem from the existing RegisterSufficiency (G&J A11 PO1). The existing problem is about DAG-based register allocation; this one is about circular arc graph coloring for loop variables with wrap-around. The issue mentions a reduction from PermutationGeneration (R226), connecting it to the reduction graph. The brute-force and ILP solver paths are identified.

Non-trivial

Pass. The circular arc coloring structure (wrap-around modular arithmetic on live ranges) is genuinely different from any existing problem in the codebase. It is not a variant of RegisterSufficiency — the input structure (circular arcs vs. DAG) and feasibility constraints (non-overlapping color assignment on a circle vs. register scheduling on a DAG) are fundamentally different.

Correctness

Fail. The example instance is incorrect.

Example error: The issue claims that for the given 5-variable instance with N=10, K=3 is NOT sufficient and K=4 is needed. This is wrong. Brute-force enumeration confirms that K=3 suffices with assignment {v1=1, v2=2, v3=1, v4=2, v5=3}:

• v1(1) ≠ v2(2) ✓, v1(1) ≠ v4(2) ✓, v1(1) ≠ v5(3) ✓
• v2(2) ≠ v3(1) ✓, v2(2) ≠ v5(3) ✓
• v3(1) ≠ v4(2) ✓, v4(2) ≠ v5(3) ✓

There are 12 valid 3-colorings out of 243 total configurations. The issue goes through multiple failed coloring attempts and incorrectly concludes K=3 is impossible, but never tries the valid assignment above.

References are correct: Tucker (1975) "Coloring a family of circular arcs" in SIAM J. Applied Math 29(3):493–502 is verified. Garey, Johnson, Miller, Papadimitriou (1980) "The complexity of coloring circular arcs and chords" in SIAM J. Algebraic and Discrete Methods 1(2):216–227 is verified (the 1978 date in the issue refers to the unpublished manuscript cited in G&J, which was published in 1980). The NP-completeness claim and polynomial-time solvability for fixed K are confirmed by the 1980 paper.

Well-written

Fail. Several issues:

1. Broken example (critical): The example section is a mess — it contains multiple failed coloring attempts with crossed-out checks, culminating in the wrong conclusion that K=4 is needed. The correct answer is K=3. The example must be rewritten with a correct solution and clean presentation.

2. Missing concrete complexity expression: The Complexity section says "O(K^|V| · poly(|V|))" but does not provide a concrete expression in terms of problem parameters suitable for declare_variants! (e.g., "num_colors^num_variables" or similar). The skill requires "a concrete complexity expression in terms of problem parameters."

3. No linked ILP rule issue: The "How to solve" section checks the ILP box and describes how to formulate as ILP, but does not link a companion [Rule] RegisterSufficiencyForLoops to ILP issue as required by the template.

4. Missing Expected Outcome section: The template requires an "Expected Outcome" section with the optimal solution and objective value. The example attempts to provide this inline but gets the answer wrong.

5. Value type concern: The issue proposes Value = Min<usize> (minimum number of registers). This is reasonable as an optimization formulation, but the G&J definition is a decision problem ("can K registers suffice?"). The issue should clarify whether this is modeled as optimization (minimize chromatic number) or feasibility (given K, is it feasible?), since the schema includes no K bound field but the definition references K.

6. Schema inconsistency with definition: The formal definition includes K as part of the input, but the Schema has no bound or k field — only loop_length and variables. If the Value type is Min<usize> (optimization), K should not be in the definition; if it's a decision problem with K, the schema needs a bound field.

Recommendations

• Rewrite the example with the correct K=3 solution: {v1=1, v2=2, v3=1, v4=2, v5=3}.
• Decide on optimization vs. decision formulation and make the schema consistent with the definition.
• Add a concrete complexity expression for declare_variants!.
• File a companion [Rule] RegisterSufficiencyForLoops to ILP issue or remove the ILP claim.

[isPANN]

Converted from decision to optimization framing: removed bound K, renamed to MinimumRegisterSufficiencyForLoops. Objective is now to minimize the number of registers (chromatic number of the circular arc intersection graph). Fixed the broken example instance. Companion rule issue to follow.

[isPANN]

Fix-issue changelog

• Associated rules: Linked [Rule] Permutation Generation to MinimumRegisterSufficiencyForLoops #874 (PermutationGeneration → MinimumRegisterSufficiencyForLoops).
• Complexity: Added concrete expression "num_variables^num_variables". Fixed reference year (1978 preprint → 1980 published).
• Schema notes: Added Value = Min<usize> and getter methods.
• ILP: Added companion rule note.
• Example: Added "no 2-coloring exists" justification.
• Added Python validation script.

Applied by /fix-issue.