Parameterized Problems on a Word RAM

Lax117284.ParameterizedComplexity · concepts/Lax117284/ParameterizedComplexity.lean · lax-117284

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.

    Natural Language Statement

    Definition

    Parameterized problems use the archive's Lax888481.ParameterizedComplexity.ProblemLax888481.ParameterizedComplexity.Problem. The decision bounds use Lax496464.WHA1FptTime.FptTimeOnLax496464.WH_A1_FptTime.FptTimeOn: one program, a computable function of the parameter, and a polynomial in binary input size. For the structural parameter involving treewidth, the time bound does not require polynomial-time computation of the parameter itself.

    The local FitsFits and DecidesDecides predicates record the unprefixed machine interface used by the scheduling programs. They are intermediate specifications; the public tractability statements use the imported fixed-parameter time definition.

    Concept map
    8 concepts; 2 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Lax496464.WH_A2_FptReductions
    2import Lax888481.ParameterizedComplexity
    3
    4/-!
    5---
    6title: Parameterized Problems on a Word RAM
    7type: definition
    8---
    9Parameterized problems use the archive's `Lax888481.ParameterizedComplexity.Problem`.
    10The decision bounds use `Lax496464.WH_A1_FptTime.FptTimeOn`: one program,
    11a computable function of the parameter, and a polynomial in binary input size.
    12For the structural parameter involving treewidth, the time bound does not require
    13polynomial-time computation of the parameter itself.
    14
    15The local `Fits` and `Decides` predicates record the unprefixed machine interface
    16used by the scheduling programs. They are intermediate specifications; the public
    17tractability statements use the imported fixed-parameter time definition.
    18-/
    19
    20namespace Lax117284.ParameterizedComplexity
    21
    22open Lax808846.Ram Lax808846.RamComputes
    23
    24abbrev Problem := Lax888481.ParameterizedComplexity.Problem
    25
    26/-- The word `x` fits at word length `w`, with room for `c` times its length: every entry
    27`v` of `x` satisfies `c * (x.length + v + 1) ^ c ≤ 2 ^ w`. -/
    28def Fits (c w : ℕ) (x : List ℕ) : Prop := ∀ v ∈ x, c * (x.length + v + 1) ^ c ≤ 2 ^ w
    29
    30open Classical in
    31/-- At every word length, the program decides `P` on every admissible word that fits,
    32within `c * g k * (|x| + 1) ^ c` instructions, where `k` is the word's parameter. It writes `1`
    33for a yes-instance and `0` for a no-instance. -/
    34def Decides (P : Problem) (prog : Program) (c : ℕ) (g : ℕ → ℕ) : Prop :=
    35 ∀ w : ℕ, ComputesInTime w prog
    36 {x | x ∈ P.Domain ∧ Fits c w x}
    37 (fun x => if P.Yes x then [1] else [0])
    38 (fun x => c * g (P.param x) * (x.length + 1) ^ c)
    39
    40/-- The shared fixed-parameter time predicate applied to a decision problem. -/
    41noncomputable abbrev FptDecision (P : Problem) : Prop :=
    42 open Classical in
    43 Lax496464.WH_A1_FptTime.FptTimeOn P.Domain P.param
    44 (fun x => if P.Yes x then [1] else [0])
    45
    46/-- Intermediate machine specification for a reduction computed by `prog` within
    47`c * g k * (|x| + 1) ^ c` instructions on the admissible words that fit and whose image fits,
    48and raising the parameter to at most `h k`. -/
    49structure MachineReduction (P Q : Problem) (f : List ℕ → List ℕ) (prog : Program)
    50 (c : ℕ) (g h : ℕ → ℕ) : Prop where
    51 /-- The image of an admissible word is admissible. -/
    52 maps_domain : ∀ x ∈ P.Domain, f x ∈ Q.Domain
    53 /-- Yes-instances go to yes-instances, and no-instances to no-instances. -/
    54 correct : ∀ x ∈ P.Domain, (P.Yes x ↔ Q.Yes (f x))
    55 /-- The new parameter is bounded by a function of the old one alone. -/
    56 param_le : ∀ x ∈ P.Domain, Q.param (f x) ≤ h (P.param x)
    57 /-- At every word length, the program computes `f` on every admissible word that fits and
    58 whose image fits, within the stated bound. -/
    59 time : ∀ w : ℕ, ComputesInTime w prog
    60 {x | x ∈ P.Domain ∧ Fits c w x ∧ Fits c w (f x)}
    61 f (fun x => c * g (P.param x) * (x.length + 1) ^ c)
    62
    63/-- The archive's shared fixed-parameter reduction relation. -/
    64abbrev FptReduces := Lax496464.WH_A2_FptReductions.FptReduces
    65
    66end Lax117284.ParameterizedComplexity
    67

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…