Parameters along special cases
Lax434175.PropagationParameters · concepts/Lax434175/PropagationParameters.lean · lax-434175
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
The transfers of parameterized results along a special case () ask that, on every word, the parameter of an instance of be at most a function of the parameter of an instance of . A parameter agrees along if, on every word, the two parameters are equal; then it is bounded with the identity.
Theorem. Let be specifications of the operations family, both with the standard encoding. Under the standard reading the parameters , , , , , , , , the number of kinds of machines, the rank of , , , the largest communication delay, the width of the precedence order, (the most time windows sharing an instant, minus one) and the maximum slack agree along , and so do their sums. The same holds for , , , , , and 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 for the makespan and at for the maximum lateness; the makespan is a special case only of itself and of the maximum lateness with all due dates , 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 , the parameter of a word of is that of the same word read for , so it is computed by the same program.
Theorem. If the reading lifts along and determines the answer for , then fixed-parameter tractability goes down from to for every parameter that agrees along .
Concept map
Evidence
This concept declares 25 statements. Each proof establishes one of them relative to its assumptions.
1 batch_n proven
2 batch_numD proven
3 batch_numP proven
4 batch_numR proven
5 batch_numW proven
6 batch_pmax proven
7 batch_wmax proven
8 isFPT_down_eq proven
9 ops_chi proven
10 ops_cmax proven
11 ops_kinds proven
12 ops_m proven
13 ops_n proven
14 ops_numD proven
15 ops_numP proven
16 ops_numR proven
17 ops_numW proven
18 ops_pmax proven
19 ops_pw proven
20 ops_qmax proven
21 ops_rank proven
22 ops_slackmax proven
23 ops_width proven
24 ops_wmax proven
25 wordEq_tplus proven
Lean source view on GitHub
| 1 | import Lax434175.Propagation |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Parameters along special cases |
| 6 | type: theorem |
| 7 | --- |
| 8 | The transfers of parameterized results along a special case |
| 9 | (`Propagation`) ask that, on every word, the parameter of an instance of be at |
| 10 | most a function of the parameter of an instance of . A parameter *agrees |
| 11 | along* if, on every word, the two parameters are equal; then it is |
| 12 | bounded with the identity. |
| 13 | |
| 14 | **Theorem.** Let be specifications of the operations family, both with |
| 15 | the standard encoding. Under the standard reading the parameters , , |
| 16 | , , , , , , the number of kinds of |
| 17 | machines, the rank of , , , the largest communication |
| 18 | delay, the width of the precedence order, (the most time windows sharing an |
| 19 | instant, minus one) and the maximum slack agree along , and so do their |
| 20 | sums. The same holds for , , , , |
| 21 | , and in the batching family. |
| 22 | |
| 23 | The words determine the kernel instance, the views and the threshold, and the |
| 24 | lift changes none of them; every parameter listed reads only those. The time |
| 25 | window of a job ends at its deadline, and also at for the makespan and at |
| 26 | for the maximum lateness; the makespan is a special case only of |
| 27 | itself and of the maximum lateness with all due dates , so the windows agree. |
| 28 | |
| 29 | Fixed-parameter tractability in the sense of lax-496464 includes that the |
| 30 | parameter is computed in polynomial time. For a parameter that agrees along |
| 31 | , the parameter of a word of is that of the same word read for , |
| 32 | so it is computed by the same program. |
| 33 | |
| 34 | **Theorem.** If the reading lifts along and determines the answer for |
| 35 | , then fixed-parameter tractability goes down from to for every |
| 36 | parameter that agrees along . |
| 37 | -/ |
| 38 | |
| 39 | namespace Lax434175.PropagationParameters |
| 40 | open Lax434175 Lax434175.Problems Lax434175.Kernels Lax434175.Assembly Lax434175.Results |
| 41 | open Lax434175.ResultParameters |
| 42 | |
| 43 | variable {K : Kernel} {F : Family K} |
| 44 | |
| 45 | /-- On every word, the parameter of `t` equals that of `s`. -/ |
| 46 | def 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 | |
| 50 | axiom 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 |
| 55 | on every word. -/ |
| 56 | axiom 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 | |
| 61 | section Ops |
| 62 | |
| 63 | variable {s t : Spec OperationsFamily.family} |
| 64 | |
| 65 | axiom 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)) |
| 68 | axiom 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)) |
| 71 | axiom 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)) |
| 74 | axiom 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)) |
| 77 | axiom 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)) |
| 80 | axiom 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)) |
| 83 | axiom 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)) |
| 86 | axiom 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)) |
| 89 | axiom 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)) |
| 92 | axiom 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)) |
| 95 | axiom 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)) |
| 98 | axiom 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)) |
| 101 | axiom 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)) |
| 104 | axiom 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 | |
| 108 | axiom 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) |
| 111 | axiom 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 | |
| 115 | end Ops |
| 116 | |
| 117 | section Batch |
| 118 | |
| 119 | variable {s t : Spec BatchFamily.family} |
| 120 | |
| 121 | axiom batch_n (h : s.le t) : |
| 122 | WordEq StandardReading.batch (lift (Batch.n s)) (lift (Batch.n t)) |
| 123 | axiom batch_pmax (h : s.le t) : |
| 124 | WordEq StandardReading.batch (lift (Batch.pmax s)) (lift (Batch.pmax t)) |
| 125 | axiom batch_numP (h : s.le t) : |
| 126 | WordEq StandardReading.batch (lift (Batch.numP s)) (lift (Batch.numP t)) |
| 127 | axiom batch_numR (h : s.le t) : |
| 128 | WordEq StandardReading.batch (lift (Batch.numR s)) (lift (Batch.numR t)) |
| 129 | axiom batch_numW (h : s.le t) : |
| 130 | WordEq StandardReading.batch (lift (Batch.numW s)) (lift (Batch.numW t)) |
| 131 | axiom batch_numD (h : s.le t) : |
| 132 | WordEq StandardReading.batch (lift (Batch.numD s)) (lift (Batch.numD t)) |
| 133 | axiom batch_wmax (h : s.le t) : |
| 134 | WordEq StandardReading.batch (lift (Batch.wmax s)) (lift (Batch.wmax t)) |
| 135 | |
| 136 | end Batch |
| 137 | |
| 138 | end Lax434175.PropagationParameters |
| 139 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments