[Model] EnsembleComputation

[isPANN]

Motivation

ENSEMBLE COMPUTATION (P301) from Garey & Johnson, A11 PO9. A classical NP-complete problem useful for reductions. It asks whether a given collection of target subsets can all be computed by a short sequence of disjoint union operations, starting from singletons or previously computed intermediate sets.

Planned reduction: MinimumVertexCover → EnsembleComputation (per Garey & Johnson, Section 3.2.2 — transformation from VERTEX COVER). See also rule issue #204.

Definition

Name: EnsembleComputation
Reference: Garey & Johnson, Computers and Intractability, A11 PO9

Mathematical definition:

INSTANCE: Collection C of subsets of a finite set A, positive integer J.
QUESTION: Is there a sequence S = (z₁ ← x₁ ∪ y₁, z₂ ← x₂ ∪ y₂, ..., zⱼ ← xⱼ ∪ yⱼ) of j ≤ J union operations, where each xᵢ and yᵢ is either {a} for some a ∈ A or z_k for some k < i, such that xᵢ and yᵢ are disjoint, 1 ≤ i ≤ j, and such that for every subset c ∈ C there exists some zᵢ, 1 ≤ i ≤ j, that is identical to c?

This is a satisfaction (decision) problem. The decision framing with budget J is the canonical formulation in the literature (Garey & Johnson, Järvisalo et al. 2012). The budget J determines the number of variables, analogous to k in KColoring.

Variables

• Count: 2 * J variables, encoding J union operations. Each operation i ∈ {1, ..., J} has two operand variables: operand1_i and operand2_i.
• Per-variable domain: Each operand variable ranges over |A| + J values (indices 0..|A| represent singletons {a} for a ∈ A; indices |A|..|A|+J represent previously computed sets z₁..zⱼ). This gives dims() = vec![|A| + J; 2 * J].
• Meaning: A configuration [op1_x, op1_y, op2_x, op2_y, ..., opJ_x, opJ_y] specifies the two operands for each of the J union operations.
• evaluate(): Returns true if and only if:
  1. For each operation i, both operands refer to valid sources (singletons or z_k with k < i — i.e., operand indices ≥ |A| must satisfy the index < |A| + i),
  2. For each operation i, the sets x_i and y_i are disjoint,
  3. Every subset c ∈ C appears as some z_i in the computed sequence.

Schema (data type)

Type name: EnsembleComputation
Variants: No generic parameters needed (elements and subsets represented by integer indices); a single concrete variant.

Field	Type	Description
universe_size	usize	Number of elements in A (elements are represented as 0..universe_size)
subsets	Vec<Vec<usize>>	The collection C: each inner Vec lists elements of one required subset
budget	usize	Maximum number of union operations J allowed

Complexity

• Decision complexity: NP-complete (Garey & Johnson, Section 3.2.2; transformation from VERTEX COVER). Remains NP-complete even if each c ∈ C satisfies |c| ≤ 3.
• Best known exact algorithm: No specialized exact algorithm is known; brute-force enumeration of the search space is the baseline approach. Each of the 2J operand variables ranges over |A| + J values, giving a brute-force complexity of O((|A| + J)^(2J)).
• declare_variants! complexity string: "(universe_size + budget)^(2 * budget)"
• References:
  • [Garey & Johnson, 1979] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979. Problem PO9, Appendix A11.
  • [Järvisalo et al., 2012] M. Järvisalo, P. Kaski, M. Koivisto, J. Korhonen, "Finding Efficient Circuits for Ensemble Computation", Proc. SAT 2012, LNCS 7317, pp. 369–382. https://doi.org/10.1007/978-3-642-31612-8_28

Extra Remark

Full book text:

INSTANCE: Collection C of subsets of a finite set A, positive integer J.
QUESTION: Is there a sequence S = (z1 ← x1 ∪ y1, z2 ← x2 ∪ y2,...,zj ← xj ∪ yj) of j ≤ J union operations, where each xi and yi is either {a} for some a ∈ A or zk for some k < i, such that xi and yi are disjoint, 1 ≤ i ≤ j, and such that for every subset c ∈ C there exists some zi, 1 ≤ i ≤ j, that is identical to c?
Reference: [Garey and Johnson, ——]. Transformation from VERTEX COVER (see Section 3.2.2).
Comment: Remains NP-complete even if each c ∈ C satisfies |c| ≤ 3. The analogous problem in which xi and yi need not be disjoint for 1 ≤ i ≤ j is also NP-complete under the same restriction.

How to solve

• It can be solved by (existing) bruteforce: enumerate all valid sequences of ≤ J disjoint-union operations over elements of A (and previously built sets), check if every c ∈ C is produced.
• It can be solved by reducing to integer programming.
• Other: N/A — no other known tractable special case applies to the general problem

Example Instance

Small satisfiable instance:

• Universe: A = {0, 1, 2, 3, 4} (5 elements)
• Required subsets: C = {{0,1,2}, {0,1,3}, {2,3,4}}
• Budget: J = 5

Brute-force complexity: (5 + 5)^(2 × 5) = 10^10 = 10 billion configurations (illustrates the rapid growth of the search space).

Witness sequence (j = 4 ≤ J = 5):

• z₁ = {0} ∪ {1} = {0,1} (disjoint ✓)
• z₂ = z₁ ∪ {2} = {0,1,2} = C[0] ✓
• z₃ = z₁ ∪ {3} = {0,1,3} = C[1] ✓
• z₄ = {2} ∪ {3} = {2,3} (disjoint ✓; intermediate set)
• z₅ = z₄ ∪ {4} = {2,3,4} = C[2] ✓

All 3 subsets in C appear (j = 5 ≤ J = 5 ✓). Note z₁ = {0,1} is reused by both z₂ and z₃, demonstrating sharing.

Greedy trap: Building each subset independently requires (|c|−1) operations per subset: 2 + 2 + 2 = 6 operations. Sharing the intermediate z₁ = {0,1} between C[0] and C[1] saves one operation, reducing the total to 5.

Why budget J = 4 is infeasible: With only 4 operations, we cannot produce all 3 target subsets. Building C[0] = {0,1,2} requires at least 2 operations (e.g., z₁ = {0}∪{1}, z₂ = z₁∪{2}). Building C[2] = {2,3,4} requires at least 2 operations (e.g., z₃ = {2}∪{3}, z₄ = z₃∪{4}). That's 4 operations consumed, but C[1] = {0,1,3} still needs z₁∪{3} — requiring a 5th operation. So J = 4 is a NO instance.

Suboptimal witness: Using J = 6 (budget exceeds need): build each subset independently without sharing — z₁={0}∪{1}, z₂=z₁∪{2}=C[0], z₃={0}∪{1}, z₄=z₃∪{3}=C[1], z₅={2}∪{3}, z₆=z₅∪{4}=C[2]. Valid but wasteful (j=6 > optimal j=5).

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Novel problem, but no planned reductions — would be an orphan node
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	⚠️ Warn	Reference is legitimate but complexity bound is vague; "Theorem 3.6" citation appears inaccurate
Well-written	❌ Fail	Variables section does not map to Problem trait; missing concrete dims()/evaluate() specification

Overall: 1 passed, 2 warnings, 1 failed

---

Usefulness

The problem does not yet exist in the reduction graph (confirmed via pred show EnsembleComputation). However, the Motivation section does not mention any planned reduction rules — neither inbound nor outbound. Adding this problem without at least one reduction rule would create an orphan node in the reduction graph with no practical value for the library. The Garey & Johnson book notes a transformation from Vertex Cover, which could serve as an inbound reduction, but this is not mentioned in the Motivation as a planned rule.

Recommendation: The issue should explicitly state at least one planned reduction (e.g., MinimumVertexCover → EnsembleComputation per the G&J transformation) to justify adding this problem.

Non-trivial

EnsembleComputation has genuinely distinct feasibility constraints from all 24 existing problems. The problem asks whether a collection of target subsets can be produced by a bounded sequence of disjoint union operations starting from singletons — this is a fundamentally different structure from graph problems (MIS, MaxClique, etc.), formula problems (SAT), set systems (SetCovering, SetPacking), algebraic problems (QUBO, ILP), or other misc problems (BinPacking, PaintShop, Factoring). No existing problem is isomorphic or a trivial variant.

Correctness

Reference verification:

• Garey & Johnson (1979) is a legitimate, authoritative reference already present in the project bibliography (docs/paper/references.bib as garey1979). The book's Appendix A catalogs over 300 NP-complete problems including a "Program Optimization" (PO) section. The claim that Ensemble Computation appears as problem PO9 in section A11 is plausible and consistent with the book's structure.
• The "Extra Remark" section reproduces what reads like authentic book text, including the note about NP-completeness when |c| ≤ 3 and the non-disjoint variant, which adds credibility.
• The claim of "Transformation from VERTEX COVER" is consistent with the G&J pattern of citing the source reduction for each problem.

Issues found:

• The issue cites "Theorem 3.6" for the NP-completeness proof, but Garey & Johnson Chapter 3 covers the general theory of NP-completeness reductions. Theorem 3.6 is unlikely to be specifically about Ensemble Computation — it is more likely a general theorem about the reduction technique. This citation is misleading.
• The complexity bound "O*(2^(|A|·J))" is acknowledged as AI-generated and unverified. No specific algorithm or paper is cited for this bound. The description "branch-and-bound or dynamic programming over subsets" is hand-waving, not a concrete algorithm reference. For a satisfaction problem, a brute-force bound should be derivable from the search space, but the claimed bound is not well-justified.

Well-written

Section completeness:

• Motivation: Present but lacks planned reductions. ⚠️
• Name: EnsembleComputation — acceptable, follows conventions (no optimization prefix needed for a satisfaction problem). ✅
• Reference: Garey & Johnson cited. ✅
• Definition: Mathematical definition is present, clear, and well-formed. ✅
• Variables: Fails. ❌
• Schema: Present with field table. ✅
• Complexity: Present but vague. ⚠️
• How to solve: Brute-force checked, but see below. ⚠️
• Example Instance: Present with satisfiable and unsatisfiable instances. ✅

Variables section failure (critical):
The Variables section describes the decision variable as "the sequence of up to J union operations" with operands chosen from singletons or previous results. This does not map to the Problem trait's required dims() -> Vec<usize> interface, which needs a fixed-length vector of per-variable domain sizes. The issue must specify:

1. How many variables there are (e.g., is it J operations, each with 2 operand choices?)
2. What is the domain of each variable (a concrete integer, not "singletons plus previously computed sets")
3. How evaluate() maps a configuration vector to bool

Without this mapping, the problem cannot be implemented against the Problem trait.

Brute-force solvability concern:
The issue checks "It can be solved by (existing) bruteforce" but the existing BruteForce solver enumerates all configurations from dims(). Since dims() is not properly defined, it is unclear whether the existing brute-force solver can actually enumerate the search space. The variable-length, dependency-structured search space (each step depends on previous results) is non-trivial to encode as a flat configuration vector.

Symbol consistency:

• The definition uses A, C, J, z_i, x_i, y_i consistently between the definition and example. ✅
• The schema uses universe_size, subsets, budget which map clearly to |A|, C, J. ✅

Example quality:
The satisfiable example (A = {0,1,2,3}, C = {{0,1,2},{0,1,3}}, J = 4) is well-chosen and fully worked through. The unsatisfiable example (A = {0,1,2}, C = {{0,1,2}}, J = 1) is also good and verifiable by hand. ✅

Recommendations

• Define a concrete encoding of the search space as a fixed-size configuration vector with per-variable domains, suitable for dims() and evaluate(). For example: J steps, each step encoded as (operand1_index, operand2_index) from a pool of available sets, yielding 2*J variables.
• Remove or correct the "Theorem 3.6" citation — either cite the specific theorem/page or simply state "NP-complete by reduction from Vertex Cover (Garey & Johnson, 1979, Appendix A, PO9)."
• Add at least one planned reduction to the Motivation section to prevent an orphan node.
• Provide a concrete complexity citation or simply state "no specialized exact algorithm known; brute-force enumeration of the search space" without the unsubstantiated O*(...) bound.

[isPANN]

Updated the issue: restored the Theorem 3.6 citation (verified against G&J book text in references/issues/rules/R18_vc_ensemblecomputation.md — Theorem 3.6 is indeed the Ensemble Computation NP-completeness proof), added concrete dims()/evaluate() specification matching the Problem trait, added planned VC → EC reduction, and removed the unsubstantiated O*() complexity bound.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; planned reduction from MinimumVertexCover
Non-trivial	✅ Pass	Distinct feasibility constraints (disjoint union sequence) from all existing problems
Correctness	⚠️ Warn	Reference citation has internal inconsistency; complexity bound is missing a concrete expression
Well-written	❌ Fail	Missing concrete complexity string; reference inconsistency between sections; no declare_variants! complexity expression provided

Overall: 2 passed, 1 warning, 1 failed

---

Usefulness

Pass. The problem EnsembleComputation does not exist in the current reduction graph (confirmed via pred show EnsembleComputation returning an error and pred list showing no match). The issue proposes a concrete reduction from MinimumVertexCover, which would connect this problem to the existing graph. The Motivation section explains the problem's classical importance (Garey & Johnson, A11 PO9) and its role in enabling new reductions.

Non-trivial

Pass. Ensemble Computation has a genuinely different feasibility structure from all 24 existing problems. It involves constructing a sequence of disjoint union operations over a universe of elements, with ordering constraints (each operation can only reference singletons or previously computed sets) and disjointness requirements. This is not isomorphic to any existing set, graph, formula, or algebraic problem in the codebase. The closest existing problems are MinimumSetCovering and MaximumSetPacking, but those involve selecting subsets from a given family, not constructing subsets via a sequence of union operations with ordering constraints.

Correctness

Warn. The issue cites Garey & Johnson correctly at the high level — the npcomplete.owu.edu database confirms Ensemble Computation is indeed problem PO9 in the Program Optimization appendix, tagged with Vertex Cover as the source of the NP-completeness transformation. However:

1. Internal reference inconsistency: The Motivation section says "Theorem 3.6, p.66 — transformation from VERTEX COVER" but the issue's own "Extra Remark" section (which quotes the book verbatim) says "Transformation from VERTEX COVER (see Section 3.2.2)." These are different references. In Garey & Johnson, Section 3.2.2 is the section containing vertex cover reductions, while Theorem 3.6 is a different result. The Motivation section should be corrected to reference "Section 3.2.2" rather than "Theorem 3.6, p.66."

2. Missing concrete complexity expression: The Complexity section says "brute-force enumeration of the search space is the baseline approach" but does not provide a concrete worst-case time bound expression suitable for declare_variants!. For implementation, a complexity string like "(universe_size + budget)^(2 * budget)" (or similar expression reflecting the actual search space) is needed. The issue should specify this.

Well-written

Fail. The issue is generally well-structured and covers most required sections, but has the following specific deficiencies:

4a — Information Completeness:

• The Complexity section does not provide a concrete best-known algorithm with a specific time bound. It only says "brute-force enumeration... is the baseline approach." A concrete expression is required for declare_variants!.

4b — Definition Completeness:

• The formal definition is adequate — it clearly specifies the input (collection C, finite set A, budget J), feasibility constraints (disjoint union operations with ordering), and the decision question. This is satisfactory.

4c — Symbol and Notation Consistency:

• The Motivation section references "Theorem 3.6, p.66" while the Extra Remark section (quoting the book) references "Section 3.2.2." This inconsistency should be resolved.
• The Variables section defines dims() = vec![|A| + J; 2 * J] which correctly reflects the encoding. Symbols are otherwise consistent.

4d — Example Quality:

• Both examples (satisfiable and unsatisfiable) are good. The satisfiable instance is fully worked with a step-by-step witness sequence. The unsatisfiable instance includes a clear explanation of why no solution exists. This is satisfactory.

Recommendations

1. Fix the reference: Change "Theorem 3.6, p.66" in the Motivation section to match the actual book text: "Transformation from VERTEX COVER (see Section 3.2.2)."
2. Add a concrete complexity expression: Provide a worst-case time bound for declare_variants!. Since each of the 2*J operand variables ranges over |A| + J values, the brute-force search space is (|A| + J)^(2*J). A suitable complexity string would be "(universe_size + budget)^(2 * budget)" — or if a tighter bound exists from the literature, cite it.
3. Consider the Järvisalo et al. (2012) paper "Finding Efficient Circuits for Ensemble Computation" which studies this problem using SAT solvers. It may contain useful algorithmic insights or tighter bounds for the complexity section.

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem; planned reduction from MinimumVertexCover
Non-trivial	✅ Pass	Distinct feasibility structure (sequential disjoint union construction)
Correctness	⚠️ Warn	G&J reference confirmed; "Theorem 3.6, p.66" citation inconsistent with issue's own Extra Remark; no concrete complexity expression
Well-written	❌ Fail	Missing Size fields section; missing concrete complexity string for declare_variants!

Overall: 2 passed, 1 warning, 1 failed

---

Usefulness

Pass. EnsembleComputation does not exist in the codebase (confirmed via pred show EnsembleComputation). The issue proposes a concrete inbound reduction from MinimumVertexCover (which exists and is well-connected in the reduction graph). This prevents the orphan-node problem flagged in the first review.

Non-trivial

Pass. Ensemble Computation has genuinely distinct feasibility constraints from all 86 existing problem types. It involves constructing a sequence of disjoint union operations with ordering dependencies (each operation can reference singletons or previously computed sets), a structure not captured by any existing graph, formula, set, or algebraic problem. The closest problems — MinimumSetCovering and MaximumSetPacking — involve selecting from a given family of subsets, not constructing subsets via ordered union operations with a disjointness invariant.

Correctness

Warn.

Reference verification:

• Garey & Johnson (1979) is in the project bibliography (garey1979). The owu.edu NP-complete problems database confirms Ensemble Computation is catalogued under Program Optimization with tag PO9 and Vertex Cover as the source reduction. Järvisalo et al. (2012, SAT conference, LNCS 7317) independently cite G&J [8] as the source of the "NP-complete Ensemble Computation problem," confirming its existence in the book.
• The claim "Remains NP-complete even if each c ∈ C satisfies |c| ≤ 3" is consistent with G&J's style of restricted-variant annotations and the local replacement proof technique used.

Citation inconsistency: The Motivation section says "Theorem 3.6, p.66 — transformation from VERTEX COVER," but the issue's own Extra Remark (quoting the book verbatim) says "see Section 3.2.2." Section 3.2.2 ("Local Replacement") begins on page 66 and describes a general proof technique, not a theorem specific to Ensemble Computation. The appendix entry for PO9 references the proof technique section, not a named theorem. The Motivation should cite the appendix entry (A11 PO9) and reference Section 3.2.2 for the proof technique, not "Theorem 3.6."

Missing concrete complexity expression: The Complexity section says "brute-force enumeration of the search space is the baseline approach" but provides no concrete worst-case time bound for declare_variants!. From the issue's own encoding: 2·J variables each with domain |A|+J, giving search space (|A|+J)^(2·J). A suitable complexity string would be "(universe_size + budget)^(2 * budget)". No specialized exact algorithm was found in the literature — Järvisalo et al. (2012) develops a SAT encoding for finding optimal circuits but does not improve the worst-case decision bound.

Example verification (subagent):

• Satisfiable instance (A={0,1,2,3}, C=[{0,1,2},{0,1,3}], J=4): Claimed witness verified correct. At least 4 distinct satisfying assignments found (including alternative construction paths), confirming the instance is non-trivial. ✅
• Unsatisfiable instance (A={0,1,2}, C=[{0,1,2}], J=1): All 16 configurations exhaustively enumerated; zero are satisfying. Confirmed NO instance. ✅

Recommendation: Järvisalo et al. (2012) "Finding Efficient Circuits for Ensemble Computation" (SAT 2012, LNCS 7317, pp. 369–382) is a relevant reference that could be added to the bibliography.

Well-written

Fail. Two specific deficiencies remain:

4a — Missing required section: Size fields.
The issue lists Schema fields (universe_size, subsets, budget) but does not include a dedicated "Size fields" section specifying getter names and their meanings (e.g., universe_size → number of elements in A, num_subsets → number of required subsets in C, budget → maximum union operations J). This section is required for [Model] issues and is used by the overhead system to validate reduction expressions.

4a — Missing concrete complexity string.
The Complexity section must provide a declare_variants!-compatible expression. Based on the encoding: "(universe_size + budget)^(2 * budget)". If a tighter bound is known, cite it.

4c — Citation inconsistency (minor).
"Theorem 3.6, p.66" in Motivation vs "Section 3.2.2" in Extra Remark — these should be reconciled (see Correctness section above).

Sections that are now adequate:

• Definition: ✅ Clear input/feasibility/decision structure
• Variables: ✅ Concrete dims()/evaluate() specification mapping to Problem trait
• Schema: ✅ Type and fields defined
• Dims: ✅ vec![|A|+J; 2*J]
• How to solve: ✅ Bruteforce checked
• Example: ✅ Both satisfiable and unsatisfiable, fully worked
• Expected Outcome: ✅ Witness sequence and impossibility argument

Recommendations

1. Add a Size fields section listing getter names: universe_size (|A|), num_subsets (|C|), budget (J)
2. Add a concrete complexity expression: "(universe_size + budget)^(2 * budget)"
3. Fix the Motivation citation: replace "Theorem 3.6, p.66" with "Appendix A11, PO9; NP-completeness via local replacement (Section 3.2.2)"
4. Consider citing Järvisalo et al. (2012) as an additional reference for SAT-based solving approaches