Draft — mutable and not usable as a dependency; its citation marks the draft state.

Lax58.RamComplexityExample

Examples — separate resource bounds and polynomial time

concepts/Lax58/RamComplexityExample.lean · lax-58

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Concept map

    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    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 inputMagnitudeinputMagnitude, 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

    1import Mathlib.Computability.Partrec
    2import Lax58.RamComplexityElab
    3
    4/-!
    5---
    6title: Examples — separate resource bounds and polynomial time
    7type: definition
    8---
    9
    10These properties describe functions on finite sequences, without asserting
    11that every function satisfies them. Encodings are selected automatically.
    12The two-input property has linear time dependence on the first sequence's
    13length and computable time and word-capacity coefficients depending only on
    14the second sequence's length. The ordinary one-input property instead uses
    15a constant word-capacity coefficient. Natural payload magnitudes are included
    16in `inputMagnitude`, not in the sequence-length time measure.
    17
    18Polynomial time below means polynomial in sequence length, under that same
    19constant-times-input-magnitude word-capacity convention. It is a word-RAM
    20notion, not a claim about polynomial time in a binary serialization. The degree
    21is an upper bound on the time exponent, not a claim of optimality.
    22-/
    23
    24namespace Lax58.RamComplexityExample
    25
    26abbrev Input := List Nat × List Nat
    27
    28/-- One program, linear in the first input, with computable dependence on
    29the 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
    34capacity. Both functions depend only on that length, not on either list's
    35contents; they are chosen once for the algorithm. -/
    36def 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. -/
    44def 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
    51sequences of length `n`, for some constant `timeCoefficient`. The degree `d`
    52is fixed before the input is supplied; degree zero permits constant time.
    53The sufficient word-capacity bound is the one specified by `TimeBounded`. -/
    54def 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.
    59The degree and coefficients may depend on `f`, but not on the runtime input.
    60This retains `TimeBounded`'s word-capacity convention. -/
    61def PolynomialTime (f : List Nat → Nat) : Prop :=
    62 ∃ d : Nat, PolynomialTimeOfDegree f d
    63
    64end Lax58.RamComplexityExample
    65

    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

    Loading discussion…