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

Results along special cases

Lax434175.Propagation · concepts/Lax434175/Propagation.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

    A specification ss that is field by field a special case of tt embeds its instances into those of tt (the lift): same kernel instance, data read with the more general values, and schedules unchanged. A reading lifts along s≤ts \le t if every word of an instance of ss 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 s≤ts \le t, every algorithm for tt is one for ss — the same program: deciding within O(T)O(T) becomes deciding within O(T∘lift)O(T \circ \mathrm{lift}), 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 ss whose lift satisfies it.

    Theorem. The standard reading of the operations family lifts along every s≤ts \le t with the same value of the encoding field, and the standard reading of the batching family lifts along every s≤ts \le t.

    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 tt if two instances of tt 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 s≤ts \le t and determine the answer for tt. Then a word of an instance of ss has the same answer for ss and for tt, and:

    1. hardness goes up, by the identity on words: NP-hardness and strong NP-hardness of ss give those of tt; W[t]-hardness for κs\kappa_s gives W[t]-hardness for κt\kappa_t if, on every word, κt\kappa_t of an instance of tt is at most a computable function of κs\kappa_s of an instance of ss, and para-NP-hardness likewise for any function;
    2. the coarse classes go down: in P, pseudo-polynomial, in P for every fixed value (with κt\kappa_t bounded by a function of κs\kappa_s on every word), and FPT (with a computable bound, for a parameter of ss computable in polynomial time).
    Concept map
    60 concepts; 2 descendants hidden
    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 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 27 statements. Each proof establishes one of them relative to its assumptions.

    1 approxKept_down proven

    2 approxWithin_down proven

    3 batch_determined proven

    5 decidesExact_down proven

    6 decidesWithin_down proven

    7 decidesWithinWide_down proven

    8 decidesWithinWide_restrict_down proven

    15 oneSidedDecidesWithin_down proven

    21 randomApproxWithin_down proven

    22 randomDecidesWithin_down proven

    27 zeroErrorDecidesWithin_down proven

    Lean source view on GitHub

    1import Lax434175.StandardReading
    2
    3/-!
    4---
    5title: Results along special cases
    6type: theorem
    7---
    8A specification ss that is field by field a special case of tt embeds its
    9instances into those of tt (the lift): same kernel instance, data read with
    10the more general values, and schedules unchanged. A reading *lifts* along
    11s≤ts \le t if every word of an instance of ss is also a word of its lift, and
    12every word that writes a schedule of the lift writes the same schedule of the
    13instance.
    14
    15**Theorem.** If the reading lifts along s≤ts \le t, every algorithm for tt is one
    16for ss — the same program: deciding within O(T)O(T) becomes deciding within
    17O(T∘lift)O(T \circ \mathrm{lift}), and likewise for approximations within a running
    18time, randomized ones and approximation schemes, with the ratio read on the lift.
    19The same holds for approximations and schemes of the kept weight, if the lift
    20keeps the total weight, and for deciding with wide words, also on the instances
    21satisfying a predicate: on those of ss whose lift satisfies it.
    22
    23**Theorem.** The standard reading of the operations family lifts along every
    24s≤ts \le t with the same value of the encoding field, and the standard reading of
    25the batching family lifts along every s≤ts \le t.
    26
    27The second theorem holds because the standard words write every field by its
    28view, and reading data with a more general value does not change its view.
    29
    30A reading *determines the answer* for tt if two instances of tt with thresholds
    31written by one word have the same threshold and the same answer.
    32
    33**Theorem.** The standard reading of the operations family determines the answer
    34for every specification with the standard encoding, and the standard reading of
    35the batching family for every specification: the words parse uniquely, give the
    36same kernel instance and the same views, and constraints and costs read only the
    37views.
    38
    39**Theorem.** Let the reading lift along s≤ts \le t and determine the answer for tt.
    40Then a word of an instance of ss has the same answer for ss and for tt, and:
    41
    421. hardness goes up, by the identity on words: NP-hardness and strong
    43 NP-hardness of ss give those of tt; W[t]-hardness for κs\kappa_s gives
    44 W[t]-hardness for κt\kappa_t if, on every word, κt\kappa_t of an instance of tt
    45 is at most a computable function of κs\kappa_s of an instance of ss, and
    46 para-NP-hardness likewise for any function;
    472. the coarse classes go down: in P, pseudo-polynomial, in P for every fixed
    48 value (with κt\kappa_t bounded by a function of κs\kappa_s on every word), and
    49 FPT (with a computable bound, for a parameter of ss computable in polynomial
    50 time).
    51-/
    52
    53namespace Lax434175.Propagation
    54open Lax434175 Lax434175.Problems Lax434175.Kernels Lax434175.Assembly Lax434175.Results
    55
    56variable {K : Kernel} {F : Family K} (hF : F.Sound) (R : Reading F)
    57
    58/-- The reading lifts along `s ≤ t`. -/
    59def 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
    63variable {hF R}
    64
    65axiom 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
    68axiom 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
    71axiom 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
    74axiom 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
    80axiom 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
    85axiom 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
    91axiom 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
    95axiom 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
    98axiom 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
    101axiom 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
    104axiom 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
    109axiom 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
    114axiom 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
    119axiom 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
    124axiom 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
    128axiom 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`. -/
    132def 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
    136axiom ops_determined {t : Spec OperationsFamily.family} (ht : t.module .encoding = .standard) :
    137 Determined StandardReading.ops t
    138
    139axiom batch_determined (t : Spec BatchFamily.family) : Determined StandardReading.batch t
    140
    141open Lax496464.WH_A2_FptReductions Lax496464.WH_B4_Hierarchies
    142
    143variable {s t : Spec F} {h : s.le t}
    144
    145axiom 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
    149axiom npHard_up (hl : Lifts hF R h) (hd : Determined R t) :
    150 NPHard (R.at s) → NPHard (R.at t)
    151
    152axiom stronglyNPHard_up (hl : Lifts hF R h) (hd : Determined R t) :
    153 StronglyNPHard (R.at s) → StronglyNPHard (R.at t)
    154
    155axiom 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
    161axiom 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
    167axiom inP_down (hl : Lifts hF R h) (hd : Determined R t) : InP (R.at t) → InP (R.at s)
    168
    169axiom pseudoPoly_down (hl : Lifts hF R h) (hd : Determined R t) :
    170 PseudoPoly (R.at t) → PseudoPoly (R.at s)
    171
    172axiom 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
    178axiom 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
    185end Lax434175.Propagation
    186
    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 ProofShow ProofShow Proof

    Discussion

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

    Loading discussion…