Results along special cases
Lax434175.Propagation · concepts/Lax434175/Propagation.lean · lax-434175
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
A specification that is field by field a special case of embeds its instances into those of (the lift): same kernel instance, data read with the more general values, and schedules unchanged. A reading lifts along if every word of an instance of is also a word of its lift, and every word that writes a schedule of the lift writes the same schedule of the instance.
Theorem. If the reading lifts along , every algorithm for is one for — the same program: deciding within becomes deciding within , and likewise for approximations within a running time, randomized ones and approximation schemes, with the ratio read on the lift. The same holds for approximations and schemes of the kept weight, if the lift keeps the total weight, and for deciding with wide words, also on the instances satisfying a predicate: on those of whose lift satisfies it.
Theorem. The standard reading of the operations family lifts along every with the same value of the encoding field, and the standard reading of the batching family lifts along every .
The second theorem holds because the standard words write every field by its view, and reading data with a more general value does not change its view.
A reading determines the answer for if two instances of with thresholds written by one word have the same threshold and the same answer.
Theorem. The standard reading of the operations family determines the answer for every specification with the standard encoding, and the standard reading of the batching family for every specification: the words parse uniquely, give the same kernel instance and the same views, and constraints and costs read only the views.
Theorem. Let the reading lift along and determine the answer for . Then a word of an instance of has the same answer for and for , and:
- hardness goes up, by the identity on words: NP-hardness and strong NP-hardness of give those of ; W[t]-hardness for gives W[t]-hardness for if, on every word, of an instance of is at most a computable function of of an instance of , and para-NP-hardness likewise for any function;
- the coarse classes go down: in P, pseudo-polynomial, in P for every fixed value (with bounded by a function of on every word), and FPT (with a computable bound, for a parameter of computable in polynomial time).
Concept map
Evidence
This concept declares 27 statements. Each proof establishes one of them relative to its assumptions.
1 approxKept_down proven
2 approxWithin_down proven
3 batch_determined proven
4 batch_lifts proven
5 decidesExact_down proven
6 decidesWithin_down proven
7 decidesWithinWide_down proven
8 decidesWithinWide_restrict_down proven
9 eptasKept_down proven
10 fptasKept_down proven
11 inP_down proven
12 inPFixed_down proven
13 isFPT_down proven
14 npHard_up proven
15 oneSidedDecidesWithin_down proven
16 ops_determined proven
17 ops_lifts proven
18 paraNPHard_up proven
19 pseudoPoly_down proven
20 ptasKept_down proven
21 randomApproxWithin_down proven
22 randomDecidesWithin_down proven
23 schemeWithin_down proven
24 stronglyNPHard_up proven
25 wHard_up proven
26 yes_iff proven
27 zeroErrorDecidesWithin_down proven
Lean source view on GitHub
| 1 | import Lax434175.StandardReading |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Results along special cases |
| 6 | type: theorem |
| 7 | --- |
| 8 | A specification that is field by field a special case of embeds its |
| 9 | instances into those of (the lift): same kernel instance, data read with |
| 10 | the more general values, and schedules unchanged. A reading *lifts* along |
| 11 | if every word of an instance of is also a word of its lift, and |
| 12 | every word that writes a schedule of the lift writes the same schedule of the |
| 13 | instance. |
| 14 | |
| 15 | **Theorem.** If the reading lifts along , every algorithm for is one |
| 16 | for — the same program: deciding within becomes deciding within |
| 17 | , and likewise for approximations within a running |
| 18 | time, randomized ones and approximation schemes, with the ratio read on the lift. |
| 19 | The same holds for approximations and schemes of the kept weight, if the lift |
| 20 | keeps the total weight, and for deciding with wide words, also on the instances |
| 21 | satisfying a predicate: on those of whose lift satisfies it. |
| 22 | |
| 23 | **Theorem.** The standard reading of the operations family lifts along every |
| 24 | with the same value of the encoding field, and the standard reading of |
| 25 | the batching family lifts along every . |
| 26 | |
| 27 | The second theorem holds because the standard words write every field by its |
| 28 | view, and reading data with a more general value does not change its view. |
| 29 | |
| 30 | A reading *determines the answer* for if two instances of with thresholds |
| 31 | written by one word have the same threshold and the same answer. |
| 32 | |
| 33 | **Theorem.** The standard reading of the operations family determines the answer |
| 34 | for every specification with the standard encoding, and the standard reading of |
| 35 | the batching family for every specification: the words parse uniquely, give the |
| 36 | same kernel instance and the same views, and constraints and costs read only the |
| 37 | views. |
| 38 | |
| 39 | **Theorem.** Let the reading lift along and determine the answer for . |
| 40 | Then a word of an instance of has the same answer for and for , and: |
| 41 | |
| 42 | 1. hardness goes up, by the identity on words: NP-hardness and strong |
| 43 | NP-hardness of give those of ; W[t]-hardness for gives |
| 44 | W[t]-hardness for if, on every word, of an instance of |
| 45 | is at most a computable function of of an instance of , and |
| 46 | para-NP-hardness likewise for any function; |
| 47 | 2. the coarse classes go down: in P, pseudo-polynomial, in P for every fixed |
| 48 | value (with bounded by a function of on every word), and |
| 49 | FPT (with a computable bound, for a parameter of computable in polynomial |
| 50 | time). |
| 51 | -/ |
| 52 | |
| 53 | namespace Lax434175.Propagation |
| 54 | open Lax434175 Lax434175.Problems Lax434175.Kernels Lax434175.Assembly Lax434175.Results |
| 55 | |
| 56 | variable {K : Kernel} {F : Family K} (hF : F.Sound) (R : Reading F) |
| 57 | |
| 58 | /-- The reading lifts along `s ≤ t`. -/ |
| 59 | def Lifts {s t : Spec F} (h : s.le t) : Prop := |
| 60 | (∀ x w, R.Encodes s w x → R.Encodes t w ((lift F hF h).map x)) ∧ |
| 61 | ∀ x w σ, R.Decodes t ((lift F hF h).map x) w σ → R.Decodes s x w σ |
| 62 | |
| 63 | variable {hF R} |
| 64 | |
| 65 | axiom decidesExact_down {s t : Spec F} {h : s.le t} (hl : Lifts hF R h) {T : Inst F t → ℤ → ℕ} : |
| 66 | DecidesExact (R.at t) T → DecidesExact (R.at s) fun x D => T ((lift F hF h).map x) D |
| 67 | |
| 68 | axiom decidesWithin_down {s t : Spec F} {h : s.le t} (hl : Lifts hF R h) {T : Inst F t → ℕ} : |
| 69 | DecidesWithin (R.at t) T → DecidesWithin (R.at s) fun x => T ((lift F hF h).map x) |
| 70 | |
| 71 | axiom decidesWithinWide_down {s t : Spec F} {h : s.le t} (hl : Lifts hF R h) {T : Inst F t → ℕ} : |
| 72 | DecidesWithinWide (R.at t) T → DecidesWithinWide (R.at s) fun x => T ((lift F hF h).map x) |
| 73 | |
| 74 | axiom decidesWithinWide_restrict_down {s t : Spec F} {h : s.le t} (hl : Lifts hF R h) |
| 75 | {φ : Inst F t → Prop} {T : {x : Inst F t // φ x} → ℕ} : |
| 76 | DecidesWithinWide ((R.at t).restrict φ) T → |
| 77 | DecidesWithinWide ((R.at s).restrict fun x => φ ((lift F hF h).map x)) |
| 78 | fun x => T ⟨(lift F hF h).map x.1, x.2⟩ |
| 79 | |
| 80 | axiom approxWithin_down {s t : Spec F} {h : s.le t} (hl : Lifts hF R h) |
| 81 | {ρ : Inst F t → ℝ} {T : Inst F t → ℕ} : |
| 82 | ApproxWithin (R.at t) ρ T → |
| 83 | ApproxWithin (R.at s) (fun x => ρ ((lift F hF h).map x)) fun x => T ((lift F hF h).map x) |
| 84 | |
| 85 | axiom randomApproxWithin_down {s t : Spec F} {h : s.le t} (hl : Lifts hF R h) |
| 86 | {ρ : Inst F t → ℝ} {T : Inst F t → ℕ} : |
| 87 | RandomApproxWithin (R.at t) ρ T → |
| 88 | RandomApproxWithin (R.at s) (fun x => ρ ((lift F hF h).map x)) |
| 89 | fun x => T ((lift F hF h).map x) |
| 90 | |
| 91 | axiom schemeWithin_down {s t : Spec F} {h : s.le t} (hl : Lifts hF R h) |
| 92 | {T : ℚ → Inst F t → ℕ} : |
| 93 | SchemeWithin (R.at t) T → SchemeWithin (R.at s) fun ε x => T ε ((lift F hF h).map x) |
| 94 | |
| 95 | axiom randomDecidesWithin_down {s t : Spec F} {h : s.le t} (hl : Lifts hF R h) {T : Inst F t → ℕ} : |
| 96 | RandomDecidesWithin (R.at t) T → RandomDecidesWithin (R.at s) fun x => T ((lift F hF h).map x) |
| 97 | |
| 98 | axiom oneSidedDecidesWithin_down {s t : Spec F} {h : s.le t} (hl : Lifts hF R h) {T : Inst F t → ℕ} : |
| 99 | OneSidedDecidesWithin (R.at t) T → OneSidedDecidesWithin (R.at s) fun x => T ((lift F hF h).map x) |
| 100 | |
| 101 | axiom zeroErrorDecidesWithin_down {s t : Spec F} {h : s.le t} (hl : Lifts hF R h) {T : Inst F t → ℕ} : |
| 102 | ZeroErrorDecidesWithin (R.at t) T → ZeroErrorDecidesWithin (R.at s) fun x => T ((lift F hF h).map x) |
| 103 | |
| 104 | axiom approxKept_down {s t : Spec F} {h : s.le t} (hl : Lifts hF R h) |
| 105 | {W : Parameters.Parameter (problem F s)} {W' : Parameters.Parameter (problem F t)} |
| 106 | (hW : ∀ x, W' ((lift F hF h).map x) = W x) {ρ : Inst F t → ℝ} : |
| 107 | ApproxKept (R.at t) W' ρ → ApproxKept (R.at s) W fun x => ρ ((lift F hF h).map x) |
| 108 | |
| 109 | axiom ptasKept_down {s t : Spec F} {h : s.le t} (hl : Lifts hF R h) |
| 110 | {W : Parameters.Parameter (problem F s)} {W' : Parameters.Parameter (problem F t)} |
| 111 | (hW : ∀ x, W' ((lift F hF h).map x) = W x) : |
| 112 | PTASKept (R.at t) W' → PTASKept (R.at s) W |
| 113 | |
| 114 | axiom eptasKept_down {s t : Spec F} {h : s.le t} (hl : Lifts hF R h) |
| 115 | {W : Parameters.Parameter (problem F s)} {W' : Parameters.Parameter (problem F t)} |
| 116 | (hW : ∀ x, W' ((lift F hF h).map x) = W x) : |
| 117 | EPTASKept (R.at t) W' → EPTASKept (R.at s) W |
| 118 | |
| 119 | axiom fptasKept_down {s t : Spec F} {h : s.le t} (hl : Lifts hF R h) |
| 120 | {W : Parameters.Parameter (problem F s)} {W' : Parameters.Parameter (problem F t)} |
| 121 | (hW : ∀ x, W' ((lift F hF h).map x) = W x) : |
| 122 | FPTASKept (R.at t) W' → FPTASKept (R.at s) W |
| 123 | |
| 124 | axiom ops_lifts (hF : OperationsFamily.family.Sound) {s t : Spec OperationsFamily.family} |
| 125 | (h : s.le t) (he : s.module .encoding = t.module .encoding) : |
| 126 | Lifts hF StandardReading.ops h |
| 127 | |
| 128 | axiom batch_lifts (hF : BatchFamily.family.Sound) {s t : Spec BatchFamily.family} |
| 129 | (h : s.le t) : Lifts hF StandardReading.batch h |
| 130 | |
| 131 | /-- The reading determines the answer for `t`. -/ |
| 132 | def Determined (R : Reading F) (t : Spec F) : Prop := |
| 133 | ∀ u y y' D D', EncodesDecision (R.at t) u y D → EncodesDecision (R.at t) u y' D' → |
| 134 | D = D' ∧ ((problem F t).Decides y D ↔ (problem F t).Decides y' D') |
| 135 | |
| 136 | axiom ops_determined {t : Spec OperationsFamily.family} (ht : t.module .encoding = .standard) : |
| 137 | Determined StandardReading.ops t |
| 138 | |
| 139 | axiom batch_determined (t : Spec BatchFamily.family) : Determined StandardReading.batch t |
| 140 | |
| 141 | open Lax496464.WH_A2_FptReductions Lax496464.WH_B4_Hierarchies |
| 142 | |
| 143 | variable {s t : Spec F} {h : s.le t} |
| 144 | |
| 145 | axiom yes_iff (hl : Lifts hF R h) (hd : Determined R t) {u : List ℕ} {x : Inst F s} {D : ℤ} |
| 146 | (hx : EncodesDecision (R.at s) u x D) : |
| 147 | (decision (R.at t)).Yes u ↔ (decision (R.at s)).Yes u |
| 148 | |
| 149 | axiom npHard_up (hl : Lifts hF R h) (hd : Determined R t) : |
| 150 | NPHard (R.at s) → NPHard (R.at t) |
| 151 | |
| 152 | axiom stronglyNPHard_up (hl : Lifts hF R h) (hd : Determined R t) : |
| 153 | StronglyNPHard (R.at s) → StronglyNPHard (R.at t) |
| 154 | |
| 155 | axiom paraNPHard_up (hl : Lifts hF R h) (hd : Determined R t) |
| 156 | {κs : TParameter (problem F s)} {κt : TParameter (problem F t)} (g : ℕ → ℕ) |
| 157 | (hκ : ∀ u x D y D', EncodesDecision (R.at s) u x D → EncodesDecision (R.at t) u y D' → |
| 158 | κt y D' ≤ g (κs x D)) : |
| 159 | ParaNPHard (R.at s) κs → ParaNPHard (R.at t) κt |
| 160 | |
| 161 | axiom wHard_up (hl : Lifts hF R h) (hd : Determined R t) (w : ℕ) |
| 162 | {κs : TParameter (problem F s)} {κt : TParameter (problem F t)} (g : ℕ → ℕ) |
| 163 | (hg : Computable g) (hκ : ∀ u x D y D', EncodesDecision (R.at s) u x D → EncodesDecision (R.at t) u y D' → |
| 164 | κt y D' ≤ g (κs x D)) : |
| 165 | WHard (R.at s) w κs → WHard (R.at t) w κt |
| 166 | |
| 167 | axiom inP_down (hl : Lifts hF R h) (hd : Determined R t) : InP (R.at t) → InP (R.at s) |
| 168 | |
| 169 | axiom pseudoPoly_down (hl : Lifts hF R h) (hd : Determined R t) : |
| 170 | PseudoPoly (R.at t) → PseudoPoly (R.at s) |
| 171 | |
| 172 | axiom inPFixed_down (hl : Lifts hF R h) (hd : Determined R t) |
| 173 | {κs : TParameter (problem F s)} {κt : TParameter (problem F t)} (g : ℕ → ℕ) |
| 174 | (hκ : ∀ u x D y D', EncodesDecision (R.at s) u x D → EncodesDecision (R.at t) u y D' → |
| 175 | κt y D' ≤ g (κs x D)) : |
| 176 | InPFixed (R.at t) κt → InPFixed (R.at s) κs |
| 177 | |
| 178 | axiom isFPT_down (hl : Lifts hF R h) (hd : Determined R t) |
| 179 | {κs : TParameter (problem F s)} {κt : TParameter (problem F t)} (g : ℕ → ℕ) |
| 180 | (hg : Computable g) (hκ : ∀ u x D y D', EncodesDecision (R.at s) u x D → EncodesDecision (R.at t) u y D' → |
| 181 | κt y D' ≤ g (κs x D)) |
| 182 | (hps : IsParameterized (parameterized (R.at s) κs)) : |
| 183 | IsFPT (R.at t) κt → IsFPT (R.at s) κs |
| 184 | |
| 185 | end Lax434175.Propagation |
| 186 |
Builds on
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments