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

Parameters along special cases

Lax434175.PropagationParameters · concepts/Lax434175/PropagationParameters.lean · lax-434175

proven

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

    Theorem

    The transfers of parameterized results along a special case s≤ts \le t (PropagationPropagation) ask that, on every word, the parameter of an instance of tt be at most a function of the parameter of an instance of ss. A parameter agrees along s≤ts \le t if, on every word, the two parameters are equal; then it is bounded with the identity.

    Theorem. Let s≤ts \le t be specifications of the operations family, both with the standard encoding. Under the standard reading the parameters nn, mm, pmax⁡p_{\max}, #p\#p, #r\#r, #w\#w, #d\#d, wmax⁡w_{\max}, the number of kinds of machines, the rank of (pij)(p_{ij}), qmax⁡q_{\max}, χ\chi, the largest communication delay, the width of the precedence order, pw(I)pw(I) (the most time windows sharing an instant, minus one) and the maximum slack agree along s≤ts \le t, and so do their sums. The same holds for nn, pmax⁡p_{\max}, #p\#p, #r\#r, #w\#w, #d\#d and wmax⁡w_{\max} in the batching family.

    The words determine the kernel instance, the views and the threshold, and the lift changes none of them; every parameter listed reads only those. The time window of a job ends at its deadline, and also at DD for the makespan and at dj+Dd_j + D for the maximum lateness; the makespan is a special case only of itself and of the maximum lateness with all due dates 00, so the windows agree.

    Fixed-parameter tractability in the sense of lax-496464 includes that the parameter is computed in polynomial time. For a parameter that agrees along s≤ts \le t, the parameter of a word of ss is that of the same word read for tt, so it is computed by the same program.

    Theorem. If the reading lifts along s≤ts \le t and determines the answer for tt, then fixed-parameter tractability goes down from tt to ss for every parameter that agrees along s≤ts \le t.

    Concept map
    61 concepts
    100%
    Conjunctive normal formAssembling problems from fieldsOne family for serial and parallel batchingBatching problems in three-field notationBatch scheduling on a single machineCommunication delaysBounds on the number of machines and jobsDeadlinesForbidden times and input encodingsInterruption as a field of parallel-machineschedulingScheduling kernelsMaximizing the minimum machine loadMachine sets and multiprocessor tasksConstraint modules and objectivesNon-preemptive scheduling on parallelmachinesCompletion-time objectivesOnline scheduling as a gameScheduling with operationsOne family for parallel machines and shopsOne family for parallel machines with andwithout preemptionParallel machinesProblems on parallel machines in three-fieldnotationParameters along embeddingsPrecedence constraints and time lagsPreemptive scheduling on parallel machinesPreemptive shop problems in three-fieldnotationPreemptive shop schedulingOptimization problems and embeddingsResults along special casesParameters along special casesSingle-machine scheduling with rejectionRelease datesPreemption with restarts on parallelmachinesParameters of the zoo's resultsThe kinds of results on scheduling problemsA single server with setup timesNo-idle shops and batch setup timesOne family for shops with and withoutpreemptionShop problems in three-field notationShop schedulingThe standard reading of scheduling instancesand schedulesThreshold reductions between objectivesTransportation delays and a transport robotScheduling problems as parameterizedproblems on wordsParameters of scheduling problemsBinary encoding of an input and a certificateThe complexity class NPThe complexity class PFixed-Parameter Time on the Word RAMFPT-Reductions, FPT, Hardness andCompletenessFinite Relational StructuresFirst-Order Formulas and the Classes Σ_tand Π_tModel Checking and Weighted FaginDefinabilityThe W-Hierarchy and the A-HierarchyNP-Hardness of a Problem on Words ofNumbersBinary encoding of finite wordsPolynomial-time computation by a wordRAMPolynomial-time computation by a TuringmachineThe word RAMComputing a function within a time boundParameterized Problems andFPT-Reductions on a Word RAM
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    This concept declares 25 statements. Each proof establishes one of them relative to its assumptions.

    Lean source view on GitHub

    1import Lax434175.Propagation
    2
    3/-!
    4---
    5title: Parameters along special cases
    6type: theorem
    7---
    8The transfers of parameterized results along a special case s≤ts \le t
    9(`Propagation`) ask that, on every word, the parameter of an instance of tt be at
    10most a function of the parameter of an instance of ss. A parameter *agrees
    11along* s≤ts \le t if, on every word, the two parameters are equal; then it is
    12bounded with the identity.
    13
    14**Theorem.** Let s≤ts \le t be specifications of the operations family, both with
    15the standard encoding. Under the standard reading the parameters nn, mm,
    16pmax⁡p_{\max}, #p\#p, #r\#r, #w\#w, #d\#d, wmax⁡w_{\max}, the number of kinds of
    17machines, the rank of (pij)(p_{ij}), qmax⁡q_{\max}, χ\chi, the largest communication
    18delay, the width of the precedence order, pw(I)pw(I) (the most time windows sharing an
    19instant, minus one) and the maximum slack agree along s≤ts \le t, and so do their
    20sums. The same holds for nn, pmax⁡p_{\max}, #p\#p, #r\#r,
    21#w\#w, #d\#d and wmax⁡w_{\max} in the batching family.
    22
    23The words determine the kernel instance, the views and the threshold, and the
    24lift changes none of them; every parameter listed reads only those. The time
    25window of a job ends at its deadline, and also at DD for the makespan and at
    26dj+Dd_j + D for the maximum lateness; the makespan is a special case only of
    27itself and of the maximum lateness with all due dates 00, so the windows agree.
    28
    29Fixed-parameter tractability in the sense of lax-496464 includes that the
    30parameter is computed in polynomial time. For a parameter that agrees along
    31s≤ts \le t, the parameter of a word of ss is that of the same word read for tt,
    32so it is computed by the same program.
    33
    34**Theorem.** If the reading lifts along s≤ts \le t and determines the answer for
    35tt, then fixed-parameter tractability goes down from tt to ss for every
    36parameter that agrees along s≤ts \le t.
    37-/
    38
    39namespace Lax434175.PropagationParameters
    40open Lax434175 Lax434175.Problems Lax434175.Kernels Lax434175.Assembly Lax434175.Results
    41open Lax434175.ResultParameters
    42
    43variable {K : Kernel} {F : Family K}
    44
    45/-- On every word, the parameter of `t` equals that of `s`. -/
    46def WordEq (R : Reading F) {s t : Spec F} (κs : TParameter (problem F s))
    47 (κt : TParameter (problem F t)) : Prop :=
    48 ∀ u x D y D', EncodesDecision (R.at s) u x D → EncodesDecision (R.at t) u y D' → κt y D' = κs x D
    49
    50axiom wordEq_tplus {R : Reading F} {s t : Spec F} {κs κs' : TParameter (problem F s)}
    51 {κt κt' : TParameter (problem F t)} :
    52 WordEq R κs κt → WordEq R κs' κt' → WordEq R (tplus κs κs') (tplus κt κt')
    53
    54/-- Fixed-parameter tractability goes down along `s ≤ t` for a parameter that agrees
    55on every word. -/
    56axiom isFPT_down_eq {hF : F.Sound} {R : Reading F} {s t : Spec F} {h : s.le t}
    57 (hl : Propagation.Lifts hF R h) (hd : Propagation.Determined R t)
    58 {κs : TParameter (problem F s)} {κt : TParameter (problem F t)} (hκ : WordEq R κs κt) :
    59 IsFPT (R.at t) κt → IsFPT (R.at s) κs
    60
    61section Ops
    62
    63variable {s t : Spec OperationsFamily.family}
    64
    65axiom ops_n (h : s.le t) (hs : s.module .encoding = .standard)
    66 (ht : t.module .encoding = .standard) :
    67 WordEq StandardReading.ops (lift (Ops.n s)) (lift (Ops.n t))
    68axiom ops_m (h : s.le t) (hs : s.module .encoding = .standard)
    69 (ht : t.module .encoding = .standard) :
    70 WordEq StandardReading.ops (lift (Ops.m s)) (lift (Ops.m t))
    71axiom ops_pmax (h : s.le t) (hs : s.module .encoding = .standard)
    72 (ht : t.module .encoding = .standard) :
    73 WordEq StandardReading.ops (lift (Ops.pmax s)) (lift (Ops.pmax t))
    74axiom ops_numP (h : s.le t) (hs : s.module .encoding = .standard)
    75 (ht : t.module .encoding = .standard) :
    76 WordEq StandardReading.ops (lift (Ops.numP s)) (lift (Ops.numP t))
    77axiom ops_numR (h : s.le t) (hs : s.module .encoding = .standard)
    78 (ht : t.module .encoding = .standard) :
    79 WordEq StandardReading.ops (lift (Ops.numR s)) (lift (Ops.numR t))
    80axiom ops_kinds (h : s.le t) (hs : s.module .encoding = .standard)
    81 (ht : t.module .encoding = .standard) :
    82 WordEq StandardReading.ops (lift (Ops.kinds s)) (lift (Ops.kinds t))
    83axiom ops_rank (h : s.le t) (hs : s.module .encoding = .standard)
    84 (ht : t.module .encoding = .standard) :
    85 WordEq StandardReading.ops (lift (Ops.rank s)) (lift (Ops.rank t))
    86axiom ops_qmax (h : s.le t) (hs : s.module .encoding = .standard)
    87 (ht : t.module .encoding = .standard) :
    88 WordEq StandardReading.ops (lift (Ops.qmax s)) (lift (Ops.qmax t))
    89axiom ops_numW (h : s.le t) (hs : s.module .encoding = .standard)
    90 (ht : t.module .encoding = .standard) :
    91 WordEq StandardReading.ops (lift (Ops.numW s)) (lift (Ops.numW t))
    92axiom ops_numD (h : s.le t) (hs : s.module .encoding = .standard)
    93 (ht : t.module .encoding = .standard) :
    94 WordEq StandardReading.ops (lift (Ops.numD s)) (lift (Ops.numD t))
    95axiom ops_wmax (h : s.le t) (hs : s.module .encoding = .standard)
    96 (ht : t.module .encoding = .standard) :
    97 WordEq StandardReading.ops (lift (Ops.wmax s)) (lift (Ops.wmax t))
    98axiom ops_chi (h : s.le t) (hs : s.module .encoding = .standard)
    99 (ht : t.module .encoding = .standard) :
    100 WordEq StandardReading.ops (lift (Ops.chi s)) (lift (Ops.chi t))
    101axiom ops_cmax (h : s.le t) (hs : s.module .encoding = .standard)
    102 (ht : t.module .encoding = .standard) :
    103 WordEq StandardReading.ops (lift (Ops.cmax s)) (lift (Ops.cmax t))
    104axiom ops_width (h : s.le t) (hs : s.module .encoding = .standard)
    105 (ht : t.module .encoding = .standard) :
    106 WordEq StandardReading.ops (lift (Ops.width s)) (lift (Ops.width t))
    107
    108axiom ops_pw (h : s.le t) (hs : s.module .encoding = .standard)
    109 (ht : t.module .encoding = .standard) :
    110 WordEq StandardReading.ops (Ops.pw s) (Ops.pw t)
    111axiom ops_slackmax (h : s.le t) (hs : s.module .encoding = .standard)
    112 (ht : t.module .encoding = .standard) :
    113 WordEq StandardReading.ops (Ops.slackmax s) (Ops.slackmax t)
    114
    115end Ops
    116
    117section Batch
    118
    119variable {s t : Spec BatchFamily.family}
    120
    121axiom batch_n (h : s.le t) :
    122 WordEq StandardReading.batch (lift (Batch.n s)) (lift (Batch.n t))
    123axiom batch_pmax (h : s.le t) :
    124 WordEq StandardReading.batch (lift (Batch.pmax s)) (lift (Batch.pmax t))
    125axiom batch_numP (h : s.le t) :
    126 WordEq StandardReading.batch (lift (Batch.numP s)) (lift (Batch.numP t))
    127axiom batch_numR (h : s.le t) :
    128 WordEq StandardReading.batch (lift (Batch.numR s)) (lift (Batch.numR t))
    129axiom batch_numW (h : s.le t) :
    130 WordEq StandardReading.batch (lift (Batch.numW s)) (lift (Batch.numW t))
    131axiom batch_numD (h : s.le t) :
    132 WordEq StandardReading.batch (lift (Batch.numD s)) (lift (Batch.numD t))
    133axiom batch_wmax (h : s.le t) :
    134 WordEq StandardReading.batch (lift (Batch.wmax s)) (lift (Batch.wmax t))
    135
    136end Batch
    137
    138end Lax434175.PropagationParameters
    139
    Show ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow Proof
    Builds on
    Used by

    none

    From Mathlib

    none

    Discussion

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

    Loading discussion…