# Smuggling NP-Hard Problems into DNA Sort — Full Model

## The Core Idea

You take an NP-hard problem (QUBO), encode its solutions as DNA strings,
sort the strings, and decode — the first string is the optimal solution.

The GPU thinks it's sorting text. It's actually solving combinatorial
optimization. That's the smuggle.

## Two Approaches

### Approach A: Monotone Rank Encoding (dna_gpu.py)

```
QUBO Matrix Q ──┐
                │    ┌─────────────────────────────┐
Brute-force     │───>│ Compute ALL 2^n energies    │
all solutions   │    │ Sort by energy              │
                │    │ Assign DNA rank = energy rank│
                │    │ (lowest energy = "AAAA")    │
                │    └─────────────┬───────────────┘
                │                  │
                │    ┌─────────────▼───────────────┐
                │    │ Sort DNA strings (GPU/CPU)  │
                │    │ "AAAA" sorts to position 0  │
                │    └─────────────┬───────────────┘
                │                  │
                │    ┌─────────────▼───────────────┐
                └───<│ Decode position 0           │
                     │ → Optimal QUBO solution     │
                     └─────────────────────────────┘
```

**Invariants:**
- DNA rank = energy rank (by construction)
- Sorting is stable (equal energies preserve order)
- Result is EXACT (no approximation)

**Limitation:** Requires O(2^n) memory — feasible only for n ≤ 20

### Approach B: Thermodynamic Encoding (dna_qubo_nn.py)

```
QUBO Matrix Q ──┐
                │    ┌─────────────────────────────┐
Solution x ─────┼───>│ x_i = 0 → low-Tm base       │
                │    │ x_i = 1 → high-Tm base      │
                │    │ tm_stack(b_i, b_{i+1})      │
                │    │   ≈ Q_{i,i+1}·x_i·x_{i+1}   │
                │    └─────────────┬───────────────┘
                │                  │
                │    ┌─────────────▼───────────────┐
                │    │ Compute Tm (thermodynamic)  │
                │    │ Tm ≈ c_1·E(x) + c_0        │
                │    └─────────────┬───────────────┘
                │                  │
                │    ┌─────────────▼───────────────┐
                │    │ Sort by Tm (not lexicographic)
                │    │ Lower Tm ≈ lower energy     │
                │    └─────────────┬───────────────┘
                │                  │
                │    ┌─────────────▼───────────────┐
                └───<│ Lowest Tm → Best solution   │
                     └─────────────────────────────┘
```

**Invariants:**
- Tm is affine in energy (for banded QUBOs): `Tm ≈ c₁·E(x) + c₀`
- Sorting by Tm ≈ sorting by energy
- Result is APPROXIMATE (correlation, not exact)

**Advantage:** Works for large n (no brute force) — samples + sorts

## The Smuggle Architecture

```
┌─────────────────────────────────────────────────────────────────────────────┐
│                         LAYER 1: PROBLEM INPUT                              │
│                                                                             │
│  NP-Hard Problem: QUBO      Max-Cut      Ising      Knapsack (as QUBO)     │
│  Input:           Q matrix   Graph G     J, h      weights, capacity        │
└─────────────────────────────┬───────────────────────────────────────────────┘
                              │
┌─────────────────────────────▼───────────────────────────────────────────────┐
│                      LAYER 2: ENCODING (Library)                            │
│                                                                             │
│  Approach A (Monotone):              Approach B (Thermodynamic):            │
│  ──────────────────────              ────────────────────────────           │
│  encode_all_solutions(Q)             nn_stack_dg() for each dinucleotide    │
│  → List[DNASolution] sorted by E     → Tm estimate for each solution        │
│                                                                             │
│  DNA sequence = energy rank          DNA sequence = QUBO solution itself    │
│  Sorting = trivial (already sorted)  Sorting = by Tm proxy                  │
│                                                                             │
│  Key: monotone LUT assigns DNA       Key: base choice encodes variable      │
│  AFTER energy computation.            value, stacking encodes interaction.  │
└─────────────────────────────┬───────────────────────────────────────────────┘
                              │
┌─────────────────────────────▼───────────────────────────────────────────────┐
│                       LAYER 3: SORT (The Smuggle)                           │
│                                                                             │
│  ┌─────────────────┐     ┌─────────────────┐     ┌──────────────────────┐  │
│  │   CPU Encode    │────>│  GPU/CPU Sort   │────>│    CPU Decode        │  │
│  │   ( disguise )  │     │  ( weapon )     │     │   ( extract result ) │  │
│  └─────────────────┘     └─────────────────┘     └──────────────────────┘  │
│                                                                             │
│  The sort operation sees:                                                   │
│    Input:  List[str] (DNA strings)                                          │
│    Output: List[str] (sorted strings)                                       │
│                                                                             │
│  The sort operation DOES NOT see:                                           │
│    - The QUBO matrix                                                        │
│    - The energy function                                                    │
│    - The optimization objective                                             │
│    - That it's solving NP-hard combinatorial optimization                   │
│                                                                             │
│  THIS IS THE SMUGGLE.                                                       │
│                                                                             │
│  The GPU's sort kernel thinks: "I'm sorting strings."                      │
│  The DNA encoding means: "These strings encode an ordering by energy."      │
│  The result is: "The first string is the optimal solution."                 │
└─────────────────────────────┬───────────────────────────────────────────────┘
                              │
┌─────────────────────────────▼───────────────────────────────────────────────┐
│                     LAYER 4: DECODE (Receipt Production)                    │
│                                                                             │
│  sorted_solutions[0]  → optimal DNASolution                                 │
│  sorted_solutions[-1] → worst DNASolution                                   │
│                                                                             │
│  Receipt: {                                                                 │
│    receiptID:   hash(Q),                                                    │
│    expression:  str(Q),                                                     │
│    finalState:  Φ (ADMIT — exact) or Λ (ADMIT — approximate),               │
│    ticCount:    n_solutions (one tick per solution evaluated),              │
│    fuelUsed:    n_vars * n_solutions (multiplication ops),                  │
│    pathCost:    Some(energy),                                               │
│    libraryRefs: ["QUBOLib", "SearchLib"],                                   │
│    verified:    True (energy computed independently).                       │
│  }                                                                          │
└─────────────────────────────────────────────────────────────────────────────┘
```

## Why This Works (The Invariant)

**Theorem:** If DNA rank = energy rank, then lexicographic sort of DNA
strings produces solutions in energy order.

**Proof:**
- Let `E(x)` be QUBO energy, `rank(x)` be energy rank (0 = lowest).
- Monotone encoding: `DNA(x) = int_to_dna(rank(x), seq_len)`.
- `int_to_dna` is strictly increasing in its integer argument.
- `rank(x)` is strictly increasing in energy (lower energy → lower rank).
- Therefore: `E(x₁) < E(x₂) → rank(x₁) < rank(x₂) → DNA(x₁) < DNA(x₂)`.
- Lexicographic sort preserves `<`.
- Therefore: first sorted DNA = lowest energy solution. ∎

## SilverSight Integration

```
┌─────────────────────────────────────────────────────────────────────────────┐
│                        SilverSight Machine                                  │
│                                                                             │
│  Expression: "min x^T Q x, x in {0,1}^n"                                   │
│                                                                             │
│  LexLib:    Parse → QUBO matrix Q, variable count n                       │
│                                                                             │
│  QUBOLib:   Q, n → encode → sort → decode → DNASolution                   │
│             (this IS the smuggle — QUBOLib is the smuggling library)        │
│                                                                             │
│  SearchLib: If n ≤ 20 → brute force (exact, returns Φ)                    │
│             If n > 20 → sample + approximate (returns Λ)                   │
│                                                                             │
│  MetricLib: Finsler distance from start state to solution state           │
│                                                                             │
│  RRCLib:    Compile receipt through 3 gates                                │
│             Type: QUBO energy is well-defined ✓                            │
│             Projection: manifold distance < 1/(xm) ✓                        │
│             Merge: no collision with existing solutions ✓                  │
│                                                                             │
│  Receipt: {                                                                 │
│    receiptID:   sha256(Q),                                                  │
│    expression:  "min x^T Q x",                                              │
│    finalState:  Φ (n ≤ 20, exact) or Λ (n > 20, approximate),              │
│    ticCount:    n_solutions,                                                │
│    fuelUsed:    n * n_solutions,                                            │
│    pathCost:    Some(optimal_energy),                                       │
│    libraryRefs: ["LexLib", "QUBOLib", "SearchLib", "MetricLib", "RRCLib"],  │
│    verified:    energy recomputed from solution vector ✓                   │
│  }                                                                          │
└─────────────────────────────────────────────────────────────────────────────┘
```

## The Receipt Chain

```
QUBO Problem → LexLib → QUBOLib → SearchLib → MetricLib → RRCLib → Receipt
                                                          ↕
                                                     AuditLib (verify)
                                                          ↕
                                                     TIC++ (each library)
```

## Scaling

| Variables (n) | Solutions (2^n) | Approach | Time | Receipt State |
|---------------|-----------------|----------|------|---------------|
| 10 | 1,024 | A: exact brute-force | 1ms | Φ (trivial) |
| 15 | 32,768 | A: exact brute-force | 10ms | Φ (trivial) |
| 20 | 1,048,576 | A: exact brute-force | 200ms | Φ (exact) |
| 25 | 33,554,432 | B: sampled (50K) | 500ms | Λ (approximate) |
| 30 | 1,073,741,824 | B: sampled (50K) | 500ms | Λ (approximate) |
| 50 | ~10^15 | B: sampled + heuristic | 1s | Ρ (tight) |

## The Deep Point

The DNA encoding is not just a representation — it's a **computational
transformation**. The act of encoding maps a discrete optimization problem
onto a continuous property (melting temperature) that can be sorted in
parallel on a GPU.

The GPU thinks: "I'm sorting strings."
The QUBO thinks: "I'm finding the minimum."
SilverSight thinks: "I'm producing a Receipt."

All three are correct. None know about the others. That's the smuggle.
