Lax58.RamComplexityExample
Examples — separate resource bounds and polynomial time
concepts/Lax58/RamComplexityExample.lean · lax-58
No public endorsements yet.
Loading review…
Sign in with ORCIDConcept map
Definition
These properties describe functions on finite sequences, without asserting that every function satisfies them. Encodings are selected automatically. The two-input property has linear time dependence on the first sequence's length and computable time and word-capacity coefficients depending only on the second sequence's length. The ordinary one-input property instead uses a constant word-capacity coefficient. Natural payload magnitudes are included in , not in the sequence-length time measure.
Polynomial time below means polynomial in sequence length, under that same constant-times-input-magnitude word-capacity convention. It is a word-RAM notion, not a claim about polynomial time in a binary serialization. The degree is an upper bound on the time exponent, not a claim of optimality.
Lean source view on GitHub
| 1 | import Mathlib.Computability.Partrec |
| 2 | import Lax58.RamComplexityElab |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Examples — separate resource bounds and polynomial time |
| 7 | type: definition |
| 8 | --- |
| 9 | |
| 10 | These properties describe functions on finite sequences, without asserting |
| 11 | that every function satisfies them. Encodings are selected automatically. |
| 12 | The two-input property has linear time dependence on the first sequence's |
| 13 | length and computable time and word-capacity coefficients depending only on |
| 14 | the second sequence's length. The ordinary one-input property instead uses |
| 15 | a constant word-capacity coefficient. Natural payload magnitudes are included |
| 16 | in `inputMagnitude`, not in the sequence-length time measure. |
| 17 | |
| 18 | Polynomial time below means polynomial in sequence length, under that same |
| 19 | constant-times-input-magnitude word-capacity convention. It is a word-RAM |
| 20 | notion, not a claim about polynomial time in a binary serialization. The degree |
| 21 | is an upper bound on the time exponent, not a claim of optimality. |
| 22 | -/ |
| 23 | |
| 24 | namespace Lax58.RamComplexityExample |
| 25 | |
| 26 | abbrev Input := List Nat × List Nat |
| 27 | |
| 28 | /-- One program, linear in the first input, with computable dependence on |
| 29 | the second input in both resource bounds. |
| 30 | |
| 31 | `timeCoefficient k` bounds the instruction allowance per first-input element |
| 32 | (including the extra unit for empty input), when the second input has length |
| 33 | `k`. `wordCoefficient k` multiplies input magnitude to give a sufficient word |
| 34 | capacity. Both functions depend only on that length, not on either list's |
| 35 | contents; they are chosen once for the algorithm. -/ |
| 36 | def LinearInFirstInput (f : Input → Nat) : Prop := |
| 37 | ∃ timeCoefficient wordCoefficient : Nat → Nat, |
| 38 | Computable timeCoefficient ∧ Computable wordCoefficient ∧ |
| 39 | RamComputableWithin f |
| 40 | (fun x => (x.1.length + 1) * timeCoefficient x.2.length) |
| 41 | (fun x => wordCoefficient x.2.length * inputMagnitude x) |
| 42 | |
| 43 | /-- An explicit time allowance and a constant word-capacity coefficient. -/ |
| 44 | def TimeBounded (f : List Nat → Nat) (timeByLength : Nat → Nat) : Prop := |
| 45 | ∃ wordCoefficient : Nat, |
| 46 | RamComputableWithin f |
| 47 | (fun xs => timeByLength xs.length) |
| 48 | (fun xs => wordCoefficient * inputMagnitude xs) |
| 49 | |
| 50 | /-- Computable in at most `timeCoefficient * (n + 1)^d` instructions on |
| 51 | sequences of length `n`, for some constant `timeCoefficient`. The degree `d` |
| 52 | is fixed before the input is supplied; degree zero permits constant time. |
| 53 | The sufficient word-capacity bound is the one specified by `TimeBounded`. -/ |
| 54 | def PolynomialTimeOfDegree (f : List Nat → Nat) (d : Nat) : Prop := |
| 55 | ∃ timeCoefficient : Nat, |
| 56 | TimeBounded f (fun n => timeCoefficient * (n + 1) ^ d) |
| 57 | |
| 58 | /-- Polynomial-time computability with some fixed natural-number degree. |
| 59 | The degree and coefficients may depend on `f`, but not on the runtime input. |
| 60 | This retains `TimeBounded`'s word-capacity convention. -/ |
| 61 | def PolynomialTime (f : List Nat → Nat) : Prop := |
| 62 | ∃ d : Nat, PolynomialTimeOfDegree f d |
| 63 | |
| 64 | end Lax58.RamComplexityExample |
| 65 |
Builds on
From Mathlib
Community review
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above; your ORCID profile must share a public name.
0 comments