While this submission is a draft, it cannot be used by other submissions.

Parameterized problems, XP and fpt-reductions

Lax119563.ParameterizedComplexity · concepts/Lax119563/ParameterizedComplexity.lean · lax-119563

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

    We follow Flum and Grohe, with deterministic multitape Turing machines as the machine model.

    • A parameterized problem is a pair (L,κ)(L, \kappa) of a language L⊆{0,1}∗L \subseteq \{0, 1\}^* and a parameterization κ ⁣:{0,1}∗→N\kappa\colon \{0, 1\}^* \to \mathbb N that is computable in polynomial time.
    • A function f ⁣:N→Nf\colon \mathbb N \to \mathbb N is computable if a deterministic multitape Turing machine computes f(k)f(k) from kk.
    • (L,κ)(L, \kappa) belongs to XP if some machine decides x∈Lx \in L in time f(κ(x))⋅(∣x∣+1)f(κ(x))f(\kappa(x)) \cdot (|x| + 1)^{f(\kappa(x))} for a computable ff.
    • An fpt-reduction from (L,κ)(L, \kappa) to (L′,κ′)(L', \kappa') is a map R ⁣:{0,1}∗→{0,1}∗R\colon \{0, 1\}^* \to \{0, 1\}^* such that
      1. x∈Lx \in L if and only if R(x)∈L′R(x) \in L';
      2. RR is computed by a machine in time f(κ(x))⋅(∣x∣+1)df(\kappa(x)) \cdot (|x| + 1)^d for a computable ff and a constant dd;
      3. κ′(R(x))≤g(κ(x))\kappa'(R(x)) \leq g(\kappa(x)) for a computable gg.
    Concept map
    6 concepts; 4 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Lax119563.BinaryEncodings
    2import Lax119563.DeterministicTime
    3
    4/-!
    5---
    6title: Parameterized problems, XP and fpt-reductions
    7type: definition
    8---
    9We follow Flum and Grohe, with deterministic multitape Turing machines as the machine model.
    10
    11* A **parameterized problem** is a pair (L,κ)(L, \kappa) of a language
    12 L⊆{0,1}∗L \subseteq \{0, 1\}^* and a parameterization κ ⁣:{0,1}∗→N\kappa\colon \{0, 1\}^* \to \mathbb N
    13 that is computable in polynomial time.
    14* A function f ⁣:N→Nf\colon \mathbb N \to \mathbb N is **computable** if a deterministic multitape
    15 Turing machine computes f(k)f(k) from kk.
    16* (L,κ)(L, \kappa) belongs to **XP** if some machine decides x∈Lx \in L in time
    17 f(κ(x))⋅(∣x∣+1)f(κ(x))f(\kappa(x)) \cdot (|x| + 1)^{f(\kappa(x))} for a computable ff.
    18* An **fpt-reduction** from (L,κ)(L, \kappa) to (L′,κ′)(L', \kappa') is a map
    19 R ⁣:{0,1}∗→{0,1}∗R\colon \{0, 1\}^* \to \{0, 1\}^* such that
    20 1. x∈Lx \in L if and only if R(x)∈L′R(x) \in L';
    21 2. RR is computed by a machine in time f(κ(x))⋅(∣x∣+1)df(\kappa(x)) \cdot (|x| + 1)^d for a computable
    22 ff and a constant dd;
    23 3. κ′(R(x))≤g(κ(x))\kappa'(R(x)) \leq g(\kappa(x)) for a computable gg.
    24
    25# Implementation notes
    26* Machines are the deterministic machines of `Lax119563.DeterministicTime`, numbers are
    27 given to them in the code `encodeNat` of the binary encodings of graph pairs, and deciding
    28 and computing within a number of steps are `DecidesExactlyWithin` and `ComputesWithin`.
    29* Computability is defined with the same machines, as in Flum and Grohe, rather than with
    30 mathlib's `Computable`; the two notions agree by a standard simulation, which is not
    31 needed here.
    32* Being parameterized (polynomial-time computable parameter) is part of membership in
    33 XP\mathsf{XP}, not of the type of parameterized problems, as in the archive's
    34 W-hierarchy (`Lax496464`).
    35-/
    36
    37open Lax119563.BinaryEncodings Lax119563.DeterministicTime
    38open Lax489179.TuringMachine (Machine Deterministic)
    39
    40namespace Lax119563.ParameterizedComplexity
    41
    42/-- A parameterized problem: a language of bit strings with a parameterization. -/
    43structure ParameterizedProblem where
    44 /-- The language. -/
    45 L : Set (List Bool)
    46 /-- The parameterization. -/
    47 κ : List Bool → ℕ
    48
    49/-- `f` is computable: a deterministic multitape machine computes `f k` from `k`. -/
    50def MachineComputable (f : ℕ → ℕ) : Prop :=
    51 ∃ M : Machine, Deterministic M ∧ ∀ k : ℕ, ∃ t : ℕ, ComputesWithin M (encodeNat k) (encodeNat (f k)) t
    52
    53/-- The parameterization of `P` is computable in polynomial time. -/
    54def IsParameterized (P : ParameterizedProblem) : Prop :=
    55 ∃ M : Machine, Deterministic M ∧ ∃ C d : ℕ,
    56 ∀ x : List Bool, ComputesWithin M x (encodeNat (P.κ x)) (C * (x.length + 1) ^ d)
    57
    58/-- **XP**: the parameterized problems decided in time `f(κ x) · (|x| + 1)^{f(κ x)}` for a
    59computable `f`. -/
    60def XP : Set ParameterizedProblem :=
    61 {P | IsParameterized P ∧ ∃ M : Machine, Deterministic M ∧ ∃ f : ℕ → ℕ, MachineComputable f ∧
    62 ∀ x : List Bool, DecidesExactlyWithin M x (x ∈ P.L) (f (P.κ x) * (x.length + 1) ^ f (P.κ x))}
    63
    64/-- `R` is an **fpt-reduction** from `P` to `Q`. -/
    65structure IsFptReduction (P Q : ParameterizedProblem) (R : List Bool → List Bool) : Prop where
    66 /-- Yes-instances go to yes-instances, and no-instances to no-instances. -/
    67 correct : ∀ x : List Bool, x ∈ P.L ↔ R x ∈ Q.L
    68 /-- `R` is computable in fpt-time. -/
    69 fpt_time : ∃ M : Machine, Deterministic M ∧ ∃ f : ℕ → ℕ, MachineComputable f ∧ ∃ d : ℕ,
    70 ∀ x : List Bool, ComputesWithin M x (R x) (f (P.κ x) * (x.length + 1) ^ d)
    71 /-- The new parameter is bounded by a computable function of the old one. -/
    72 param_bounded : ∃ g : ℕ → ℕ, MachineComputable g ∧ ∀ x : List Bool, Q.κ (R x) ≤ g (P.κ x)
    73
    74/-- `P` fpt-reduces to `Q`. -/
    75def FptReduces (P Q : ParameterizedProblem) : Prop := ∃ R, IsFptReduction P Q R
    76
    77end Lax119563.ParameterizedComplexity
    78

    Implementation notes

    • Machines are the deterministic machines of Lax119563.DeterministicTimeLax119563.DeterministicTime, numbers are given to them in the code encodeNatencodeNat of the binary encodings of graph pairs, and deciding and computing within a number of steps are DecidesExactlyWithinDecidesExactlyWithin and ComputesWithinComputesWithin.
    • Computability is defined with the same machines, as in Flum and Grohe, rather than with mathlib's ComputableComputable; the two notions agree by a standard simulation, which is not needed here.
    • Being parameterized (polynomial-time computable parameter) is part of membership in XP\mathsf{XP}, not of the type of parameterized problems, as in the archive's W-hierarchy (Lax496464Lax496464).

    Discussion

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

    Loading discussion…