Parameterized problems, XP and fpt-reductions
Lax119563.ParameterizedComplexity · concepts/Lax119563/ParameterizedComplexity.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
We follow Flum and Grohe, with deterministic multitape Turing machines as the machine model.
- A parameterized problem is a pair of a language and a parameterization that is computable in polynomial time.
- A function is computable if a deterministic multitape Turing machine computes from .
- belongs to XP if some machine decides in time for a computable .
- An fpt-reduction from to is a map
such that
- if and only if ;
- is computed by a machine in time for a computable and a constant ;
- for a computable .
Concept map
Lean source view on GitHub
| 1 | import Lax119563.BinaryEncodings |
| 2 | import Lax119563.DeterministicTime |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Parameterized problems, XP and fpt-reductions |
| 7 | type: definition |
| 8 | --- |
| 9 | We follow Flum and Grohe, with deterministic multitape Turing machines as the machine model. |
| 10 | |
| 11 | * A **parameterized problem** is a pair of a language |
| 12 | and a parameterization |
| 13 | that is computable in polynomial time. |
| 14 | * A function is **computable** if a deterministic multitape |
| 15 | Turing machine computes from . |
| 16 | * belongs to **XP** if some machine decides in time |
| 17 | for a computable . |
| 18 | * An **fpt-reduction** from to is a map |
| 19 | such that |
| 20 | 1. if and only if ; |
| 21 | 2. is computed by a machine in time for a computable |
| 22 | and a constant ; |
| 23 | 3. for a computable . |
| 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 | , not of the type of parameterized problems, as in the archive's |
| 34 | W-hierarchy (`Lax496464`). |
| 35 | -/ |
| 36 | |
| 37 | open Lax119563.BinaryEncodings Lax119563.DeterministicTime |
| 38 | open Lax489179.TuringMachine (Machine Deterministic) |
| 39 | |
| 40 | namespace Lax119563.ParameterizedComplexity |
| 41 | |
| 42 | /-- A parameterized problem: a language of bit strings with a parameterization. -/ |
| 43 | structure 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`. -/ |
| 50 | def 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. -/ |
| 54 | def 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 |
| 59 | computable `f`. -/ |
| 60 | def 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`. -/ |
| 65 | structure 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`. -/ |
| 75 | def FptReduces (P Q : ParameterizedProblem) : Prop := ∃ R, IsFptReduction P Q R |
| 76 | |
| 77 | end Lax119563.ParameterizedComplexity |
| 78 |
Implementation notes
- Machines are the deterministic machines of , numbers are given to them in the code of the binary encodings of graph pairs, and deciding and computing within a number of steps are and .
- Computability is defined with the same machines, as in Flum and Grohe, rather than with mathlib's ; the two notions agree by a standard simulation, which is not needed here.
- Being parameterized (polynomial-time computable parameter) is part of membership in , not of the type of parameterized problems, as in the archive's W-hierarchy ().
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments