npWorkload
npWorkload n equals 2 to the power n and counts the minimum distinguishable comparisons needed to certify an NP-search witness whose search space has size 2^n. Researchers deriving substrate-dependent runtime bounds in the Recognition Science model cite this definition when converting bounded BIT bandwidth into exponential lower bounds on certification cycles. The declaration is a direct abbreviation that introduces no lemmas or proof obligations.
claimLet $w(n) := 2^n$ denote the minimum number of distinguishable comparisons required to certify an NP-search witness of size $n$.
background
The module derives structural lower bounds on recognition time from bounded BIT bandwidth. The recognition operator on a finite-state substrate performs at most $B · t$ useful comparisons in $t$ cycles, where $B$ is set by consciousnessGap D times the eight-tick octave. npWorkload supplies the workload side of every budget comparison: an NP-search problem whose witness search space has cardinality $2^n$ requires exactly $2^n$ distinguishable comparisons for certification. This yields a phi-rung lower bound rather than a classical Turing separation of P and NP.
proof idea
The declaration is a direct definition that sets npWorkload n to equal the exponential $2^n$ with no lemmas or tactics applied.
why it matters in Recognition Science
npWorkload supplies the workload term in certify_requires_budget, cycles_lower_bound, doubling_separation, and pvsNP_one_statement. These theorems convert the definition into the concrete bound that any recognition substrate needs at least roughly $2^n / 360$ cycles to certify an NP witness of size n. The definition fills the workload half of the module's master certificate and supports the doubling property that each added input bit doubles the required budget. It remains a substrate-dependent bound tied to the eight-tick octave and consciousnessGap; its falsifier is a physical demonstration of polynomial-time solution for NP-hard problems on a compatible recognition substrate.
scope and limits
- Does not establish a classical separation between P and NP in the Turing sense.
- Does not apply to oracles or hypercomputational substrates.
- Does not quantify the precise constant factor arising from consciousnessGap D.
- Does not address average-case or heuristic complexity.
Lean usage
theorem certify_requires_budget {n t : ℕ} (h : bandwidthBudget t ≥ npWorkload n) : bitBandwidthPerCycle * t ≥ 2 ^ n := by unfold bandwidthBudget npWorkload at h; exact hformal statement (Lean)
67def npWorkload (n : ℕ) : ℕ := 2 ^ n
proof body
Definition body.
68