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

Results between parameters of one problem

Lax434175.Domination · concepts/Lax434175/Domination.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 parameter κ′\kappa' of a problem is dominated by a parameter κ\kappa if κ′(x,D)≤g(κ(x,D))\kappa'(x, D) \le g(\kappa(x, D)) for a function gg and every instance xx and threshold DD. Then the identity on words is an fpt-reduction from the problem with κ\kappa to the problem with κ′\kappa' when gg is computable, and the words with κ≤k\kappa \le k are among those with κ′≤g(0)+⋯+g(k)\kappa' \le g(0) + \dots + g(k).

    Theorem. If κ′\kappa' is dominated by κ\kappa, then para-NP-hardness and W[t]-hardness for κ\kappa hold for κ′\kappa', and membership in XP and fixed-parameter tractability for κ′\kappa' hold for κ\kappa (gg computable for the last two).

    Two dominations of the zoo's parameters: a summand is dominated by a sum, and on the operations family the number #p\#p of distinct processing times is at most pmax⁡+1p_{\max} + 1 (the values lie in {0,…,pmax⁡}\{0, \dots, p_{\max}\}).

    Theorem. These dominations hold.

    Concept map
    59 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 jobsDeadlinesResults between parameters of one problemForbidden 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 embeddingsSingle-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 schedulingThreshold 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 7 statements. Each proof establishes one of them relative to its assumptions.

    1 inPFixed_of_dominated proven

    4 ops_numP_pmax proven

    5 paraNPHard_of_dominated proven

    6 right_tplus proven

    Lean source view on GitHub

    1import Lax434175.ResultParameters
    2
    3/-!
    4---
    5title: Results between parameters of one problem
    6type: theorem
    7---
    8A parameter κ′\kappa' of a problem is *dominated* by a parameter κ\kappa if
    9κ′(x,D)≤g(κ(x,D))\kappa'(x, D) \le g(\kappa(x, D)) for a function gg and every instance xx and
    10threshold DD. Then the identity on words is an fpt-reduction from the problem
    11with κ\kappa to the problem with κ′\kappa' when gg is computable, and the
    12words with κ≤k\kappa \le k are among those with κ′≤g(0)+⋯+g(k)\kappa' \le g(0) + \dots + g(k).
    13
    14**Theorem.** If κ′\kappa' is dominated by κ\kappa, then para-NP-hardness and
    15W[t]-hardness for κ\kappa hold for κ′\kappa', and membership in XP and
    16fixed-parameter tractability for κ′\kappa' hold for κ\kappa (gg computable for
    17the last two).
    18
    19Two dominations of the zoo's parameters: a summand is dominated by a sum, and
    20on the operations family the number #p\#p of distinct processing times is at
    21most pmax⁡+1p_{\max} + 1 (the values lie in {0,…,pmax⁡}\{0, \dots, p_{\max}\}).
    22
    23**Theorem.** These dominations hold.
    24-/
    25
    26namespace Lax434175.Domination
    27open Lax434175 Lax434175.Problems Lax434175.Results Lax434175.ResultParameters
    28open Lax496464.WH_A2_FptReductions
    29
    30variable {P : Problem}
    31
    32/-- `κ'` is bounded by `g` of `κ` on every instance and threshold. -/
    33def Dominated (κ' κ : TParameter P) (g : ℕ → ℕ) : Prop := ∀ x D, κ' x D ≤ g (κ x D)
    34
    35axiom paraNPHard_of_dominated {R : PReading P} {κ κ' : TParameter P} {g : ℕ → ℕ}
    36 (h : Dominated κ' κ g) : ParaNPHard R κ → ParaNPHard R κ'
    37
    38axiom wHard_of_dominated {R : PReading P} {κ κ' : TParameter P} {g : ℕ → ℕ} (t : ℕ)
    39 (hg : Computable g) (h : Dominated κ' κ g) : WHard R t κ → WHard R t κ'
    40
    41axiom inPFixed_of_dominated {R : PReading P} {κ κ' : TParameter P} {g : ℕ → ℕ}
    42 (h : Dominated κ' κ g) : InPFixed R κ' → InPFixed R κ
    43
    44axiom isFPT_of_dominated {R : PReading P} {κ κ' : TParameter P} {g : ℕ → ℕ}
    45 (hg : Computable g) (h : Dominated κ' κ g) (hp : IsParameterized (parameterized R κ)) :
    46 IsFPT R κ' → IsFPT R κ
    47
    48axiom left_tplus (κ κ' : TParameter P) : Dominated κ (tplus κ κ') id
    49
    50axiom right_tplus (κ κ' : TParameter P) : Dominated κ' (tplus κ κ') id
    51
    52axiom ops_numP_pmax (s : Assembly.Spec OperationsFamily.family) :
    53 Dominated (lift (Ops.numP s)) (lift (Ops.pmax s)) (· + 1)
    54
    55end Lax434175.Domination
    56
    Show 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…