Parameterized Problems on a Word RAM
Lax117284.ParameterizedComplexity · concepts/Lax117284/ParameterizedComplexity.lean · lax-117284
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
Parameterized problems use the archive's . The decision bounds use : 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 and 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
Lean source view on GitHub
| 1 | import Lax496464.WH_A2_FptReductions |
| 2 | import Lax888481.ParameterizedComplexity |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Parameterized Problems on a Word RAM |
| 7 | type: definition |
| 8 | --- |
| 9 | Parameterized problems use the archive's `Lax888481.ParameterizedComplexity.Problem`. |
| 10 | The decision bounds use `Lax496464.WH_A1_FptTime.FptTimeOn`: one program, |
| 11 | a computable function of the parameter, and a polynomial in binary input size. |
| 12 | For the structural parameter involving treewidth, the time bound does not require |
| 13 | polynomial-time computation of the parameter itself. |
| 14 | |
| 15 | The local `Fits` and `Decides` predicates record the unprefixed machine interface |
| 16 | used by the scheduling programs. They are intermediate specifications; the public |
| 17 | tractability statements use the imported fixed-parameter time definition. |
| 18 | -/ |
| 19 | |
| 20 | namespace Lax117284.ParameterizedComplexity |
| 21 | |
| 22 | open Lax808846.Ram Lax808846.RamComputes |
| 23 | |
| 24 | abbrev 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`. -/ |
| 28 | def Fits (c w : ℕ) (x : List ℕ) : Prop := ∀ v ∈ x, c * (x.length + v + 1) ^ c ≤ 2 ^ w |
| 29 | |
| 30 | open Classical in |
| 31 | /-- At every word length, the program decides `P` on every admissible word that fits, |
| 32 | within `c * g k * (|x| + 1) ^ c` instructions, where `k` is the word's parameter. It writes `1` |
| 33 | for a yes-instance and `0` for a no-instance. -/ |
| 34 | def 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. -/ |
| 41 | noncomputable 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, |
| 48 | and raising the parameter to at most `h k`. -/ |
| 49 | structure 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. -/ |
| 64 | abbrev FptReduces := Lax496464.WH_A2_FptReductions.FptReduces |
| 65 | |
| 66 | end Lax117284.ParameterizedComplexity |
| 67 |
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments