1. Executive Summary & Purpose
This report provides a formal technical evaluation of four search engine paradigms developed within the Term Rewriting System (TRS) research program for solving the Subset Sum Problem and its Exact-Cardinality extension (ECSS).
The primary objective of these search engines is to explore deterministic state-compression mechanisms capable of reducing exponential search spaces into polynomial decision structures without violating witness safety. The four engines evaluated in this report are:
- Biological Search Engine: A memoized include/exclude recurrence governed by an activation window (suffix-sum feasibility gate).
- One-Tag (Generative-Tag) Engine: An exact suffix reachability engine that materializes set-based tags for candidate decoding.
- Double-Tag Search Engine: A two-coordinate structural signature framework Δi(x) = (τi(x), κi(x)) designed for correlated state merging.
- Two-Pile / NP-Side Engine (ECSS Engine): A decoupled two-stage architecture featuring candidate isolation via structural signatures followed by independent verifier execution.
2. Integrated Architecture Process Flow
The following architecture diagram illustrates the unified execution pipeline across the four search engine paradigms, highlighting candidate generation, filtering, state merging, and independent verification:
(Suffix Sum)
(
Tagi Sets)(
Δi = (τi, κi))Signature
Exact Witness Verified
Exhausted or Search Limit Reached
3. Comparative Engine Matrix
The table below provides a structured side-by-side comparison of the four engine paradigms regarding operational state, pruning/reduction mechanism, and worst-case complexity profile:
| Engine Paradigm | Core Operational State | Pruning / Reduction Mechanism | Complexity Boundary |
|---|---|---|---|
| 1. Biological Search | State (i, d) [Index, Remaining Demand] |
Suffix-sum activation window check: d < 0 or d > ∑j=in−1 aj |
Pseudopolynomial V ≤ (n+1)(t+1) (exponential in binary length N = |x|) |
| 2. One-Tag (Generative) | Tagi = FrozenSet({sums}) Suffix reachable totals |
Exact suffix reachable set construction: Tagi = Tagi+1 ∪ (Tagi+1 + wi) |
O(1) query & O(n) decode; up to O(2n) worst-case space |
| 3. Double-Tag Engine | Δi(x) = (τi(x), κi(x)) [Residue/Tag, Metric] |
Dual-coordinate hash/signature matching; state merging under Common-Key Safety | Merge-candidate compression; requires contextual equivalence guard (Lemma E) |
| 4. Two-Pile / NP-Side | Candidate Subset J (|J| = k, ∑j∈J aj = T) |
Stage 1: Structural Signature Filter Stage 2: Independent Verifier V(I, w) = 1 |
O(n) sound certification; strictly reports UNRESOLVED on budget exhaustion |
4. Deep Dive into Individual Engine Architectures
4.1 The Biological Search Engine
Source: biological_search_engine.pyModeled after biological activation thresholds, this engine traverses a binary decision tree (include/exclude position i) where each state is represented by (i, d). Before expanding a state, the engine checks whether d < 0 or d > suffix_sum[i]. If either condition holds, the state is rejected immediately (activation rejection). While it eliminates impossible subtrees early and utilizes dynamic programming memoization, its worst-case state space V ≤ (n+1)(t+1) remains pseudopolynomial in target t, scaling exponentially relative to binary input size N = |x|.
4.2 The One-Tag (Generative-Tag) Engine
Source: tag_search_engine.py
Operates strictly backward from suffix n to index 0, generating the exact set of all achievable subset sums reachable from each suffix i. Once Tag0 is constructed, decision reporting is O(1) (target ∈ Tag0). If YES, an exact witness is extracted in n linear steps without backtracking. However, the size of Tagi can grow up to O(2n−i) distinct integers, incurring exponential space complexity O(2n) in the worst case.
4.3 The Double-Tag Search Engine
Source: DOUBLE_TAG_STATUS.txt
Replaces scalar exact-sum tags with a two-coordinate tuple Δi(x) = (τi(x), κi(x)), combining a modular residue profile with a cardinality or sum-bound metric. Two states receiving identical double tags are treated as candidates for state merging under the Common-Key Safety principle. Crucially, equal double tags are merge candidates—not automatic authorization for destructive state collapsing—requiring future contextual equivalence to prevent merging a YES path with a NO path.
4.4 The Two-Pile / NP-Side Search Engine (ECSS Engine)
Source: trs_np_side_engine.pyA decoupled, two-stage architecture designed for Exact-Cardinality Subset Sum (ECSS):
- Stage 1 (P-Side Structural Filter): Generates candidate indices and applies a structural signature check:
(chosen_count, exact_sum, remaining_demand). - Stage 2 (NP-Side Independent Verifier): Rechecks the candidate key against the original input instance independently (V(I, w) = 1), verifying index distinctness, cardinality k, and exact sum T. If search limits are reached during candidate scan, the engine strictly reports
UNRESOLVEDrather than misclassifying the instance asNO.
5. Formal Proof Obligations & Scientific Boundaries
To align these experimental implementations with Millennium Prize standards (Clay Mathematics Institute formulation), any complete solver derived from these engines must satisfy four strict proof obligations:
- 1. Obligation A (Information Preservation): Input transformations g(f(I)) = I must preserve feasibility semantics across boundaries.
-
2. Obligation B (Existence Preservation / Common-Key Safety): State compression must guarantee that no valid completion path is dropped on
YESinstances: Feas(Ft) ⟹ ∃ c ∈ Ft, ResidualFeas(I, c). - 3. Obligation C (Independent Certification): Witness recovery must output an explicit candidate checked by an independent O(n) verifier V(I, w) = 1.
- 4. Obligation D (Worst-Case Work Accounting): The total execution bit operations must be bounded by a uniform polynomial TK(N) ≤ C(N+1)k across all worst-case legal inputs of binary length N.
6. Strategic Outlook & Recommendations
- Current Status: All four engines provide robust, mathematically sound reference implementations for empirical testing and local verification.
- Open Research Frontier: While the NP-side engine guarantees O(n) verification safety and the Biological/Tag engines enforce exact decision correctness, the uniform state-bound (Lemma E) remains the open mathematical boundary required to convert pseudopolynomial execution into an unconditional proof.
- Recommended Focus: Advance the formalization of the Double-Tag / Modular Key pipeline in Lean 4 to investigate whether correlated residue signatures can maintain Common-Key Safety without state growth explosion.