Executive Technical Report · Report ID: GC-TR-2026-01 · Toward P vs. NP Research Program

Comparative Analysis of Term Rewriting System (TRS) Search Engines

Comparative Architecture, Formal Mechanics, and Complexity Boundaries of Biological, One-Tag, Double-Tag, and Two-Pile / NP-Side Search Engines
Author Gerald Clerge (“The OG of Logic”)
Prepared For CMI Research Review & Computational Complexity Group
Publication Date October 26, 2026
Document Status Formal Technical Report (Open-Access)
← All Publications ✉️ Peer Review / Inquiry

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:

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.py

Modeled 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.py

A 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 UNRESOLVED rather than misclassifying the instance as NO.

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:

The 4 Proof Obligations (CMI Compliance Framework)
  1. 1. Obligation A (Information Preservation): Input transformations g(f(I)) = I must preserve feasibility semantics across boundaries.
  2. 2. Obligation B (Existence Preservation / Common-Key Safety): State compression must guarantee that no valid completion path is dropped on YES instances: Feas(Ft) ⟹ ∃ c ∈ Ft, ResidualFeas(I, c).
  3. 3. Obligation C (Independent Certification): Witness recovery must output an explicit candidate checked by an independent O(n) verifier V(I, w) = 1.
  4. 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.