Relaxation — softening logic toward optimization
Parent: logic
Classical logic is hard-edged: a formula is true or false, a problem decidable or not, a constraint satisfied or violated. Engineering can't live there — "is this controller stable?" answered by undecidable helps no one. Relaxation is the systematic move of softening a hard/binary/exact logical notion into a graded/approximate/continuous one. Following these relaxations is exactly how you walk out of logic and into optimization — where everything is a number to improve rather than a predicate to satisfy.
The axes (each a child)
- relaxing-undecidability — soften decidability: δ-decidable, one-sided certificates, bounded horizon, generic-case (can we even decide it?).
- hard-to-soft-constraints — soften satisfaction: a hard constraint (SAT / CSP) becomes a cost to minimize (MaxSAT, penalties) — find any → find best. The doorway to optimization.
- continuous-relaxation — soften the domain: relax discrete
{0,1}to continuous[0,1], solve the easy continuous problem, round back (LP / SDP relaxation). - (further axes to add: exact → ε-approximate; binary truth → graded/fuzzy/probabilistic truth.)
Why this is the bridge to optimization
Logic asks "is there a solution?" — a yes/no predicate. Optimization asks "what's the best solution, and how close can we get?" — a real-valued objective + tolerance. Every relaxation swaps a predicate for a quantity:
| logic (hard) | relaxed (soft) |
|---|---|
| satisfied / violated | number of violations (cost) |
| decidable / not | decidable up to δ |
| exact | ε-close |
| true / false | degree of truth [0,1] |
x ∈ {0,1} | x ∈ [0,1] |
Once the answer is a quantity to improve rather than a bit to decide, search/gradient/duality methods apply — you are doing optimization.
North star — every softening is "up to δ", and δ = P×C
Relaxation is not a licence to run wild. Soften a hard wall without a bound and the process just wanders forever (drift-is-world-wandering) — you've replaced "undecidable" with "diverges anyway." So every axis carries an "up to δ" tolerance, and in the recursive-harness that δ is realized as P×C: the budget you spend is the tolerance you buy. A tighter δ (or higher confidence 1−α) costs more P×C.
Softening replaces a hard logical wall with a soft budget wall — and P×C is that wall.
Worked out for checkpoints — where the tolerance becomes a neighborhood and deviation becomes an observable δ — in gate-theory.
The exchange rate — what a digit of tolerance costs
"Up to δ" always has a price in budget (samples, iterations, compute), and the price schedule depends on the STRUCTURE you have. The core theorems of each field are exactly entries in this price list.
| structure | price of tolerance | where proved |
|---|---|---|
contraction k < 1 (verified loop) | O(log(1/δ)) steps — each extra digit of precision costs a constant | inexact-contraction |
| strongly convex + smooth optimization | O(log(1/δ)) iterations | gradient descent |
| merely convex, smooth | O(1/δ) iterations | first-order methods |
| nonsmooth or stochastic gradients | O(1/δ²) | SGD analysis |
| statistical estimation (agnostic PAC) | m = Θ((d + log(1/α))/δ²) samples | fundamental-theorem |
| verifying a probabilistic claim by sampling | O((1/δ²)·log(1/α)) samples | Chernoff bounds |
| no structure at all (blind search) | exponential | no free lunch |
Structure is what makes tolerance affordable — under contraction each additional digit of precision costs a constant (log), under 1/δ² it costs 100×; contraction is the gold standard, which is why the harness invests everything in making its loop contractive; in the harness this table is the price list that P×C pays against.
No free lunch
Relaxation relocates hardness, it doesn't repeal it: δ-decidability keeps an undecidable exact boundary; an LP relaxation has an integrality gap; MaxSAT is still NP-hard. You trade a sliver of exactness/completeness for tractability and continuity.