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

Hardness of P | M_j | Σ w_j Z_j

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

    Read through interval scheduling with eligible machine sets (lax-888481), the zoo problem P∣Mj∣∑wjZjP \mid M_j \mid \sum w_j Z_j inherits the two hardness results of that problem.

    W[1]-hardness for the number of machines. Multicoloured Clique, parameterized by the number of colours, fpt-reduces to interval scheduling parameterized by the number of machines (Theorem 1 of lax-888481), and that problem fpt-reduces to P∣Mj∣∑wjZjP \mid M_j \mid \sum w_j Z_j parameterized by the number of machines, by padding. Both reductions are strict fpt-reductions of the archive, computed by word RAM programs in linear fixed-parameter time; they raise the parameter by computable functions of it, and the numbers they write are below 2e(k) (∣x∣+1)2^{e(k)\,(|x|+1)} for a computable ee, where ∣x∣|x| is the bit size of the input and kk its parameter. So both are fpt-reductions in the sense of lax-496464, and so is their composition.

    Theorem. Multicoloured Clique fpt-reduces to P∣Mj∣∑wjZjP \mid M_j \mid \sum w_j Z_j parameterized by the number of machines. Since Multicoloured Clique is W[1]-complete (lax-496464), the problem is W[1]-hard.

    NP-hardness for pmax⁡≤25p_{\max} \le 25. For an interval scheduling instance II, let I′I' be its padding: a job without an eligible machine gets one new machine and weight 00. Read I′I' as an instance of P∣Mj∣∑wjZjP \mid M_j \mid \sum w_j Z_j with threshold ∑jwj′−∑jwj\sum_j w'_j - \sum_j w_j, the total weight of I′I' minus the total weight of II.

    Theorem. Deciding this instance is NP-hard already on the interval scheduling instances with processing times at most 2525 and unit weights: every language in NP reduces to it by a polynomial-time Turing machine writing the encoding of II. On such an instance the threshold is met exactly when every job of II can be scheduled, which is NP-hard by Theorem 2 of lax-888481. Padding keeps the processing times, so the zoo instances have pmax⁡≤25p_{\max} \le 25, and the problem is para-NP-hard for pmax⁡p_{\max}.

    Concept map
    56 concepts
    100%
    Compressed sparse row encoding of a graphA graph with a parameter appendedConjunctive normal formBinary encoding of CNF formulasPolynomial many-one reductions andNP-completenessThe satisfiability language and verifierAssembling problems from fieldsCommunication delaysBounds on the number of machines and jobsDeadlinesForbidden times and input encodingsInterval scheduling with eligible machine setsas a zoo problemHardness of P | M_j | Σ w_j Z_jScheduling kernelsMachine sets and multiprocessor tasksConstraint modules and objectivesNon-preemptive scheduling on parallelmachinesCompletion-time objectivesParallel machinesProblems on parallel machines in three-fieldnotationParameters along embeddingsPrecedence constraints and time lagsPreemptive scheduling on parallel machinesOptimization problems and embeddingsRelease datesPreemption with restarts on parallelmachinesA single server with setup timesShop schedulingThreshold reductions between objectivesBinary 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-HierarchyClique, Independent Set and Dominating SetMulticoloured Clique Is W[1]-CompleteBinary encoding of finite wordsPolynomial-time computation by a wordRAMThe word RAMComputing a function within a time boundBinary Encoding of a Scheduling InstanceWord Encoding of a (3,4) FormulaWord Encoding of a Scheduling InstanceMulticoloured CliqueNP-Hardness of a Scheduling Problem, andon a Class of InstancesParameterized Problems andFPT-Reductions on a Word RAMPolynomial-Time Many-One Reductions onthe Word RAM(3,4)-SatisfiabilityInterval Scheduling with Eligible MachineSetsThe Scheduling Problems, ParameterizedScheduling Every Job Is Hard for ConstantProcessing Times and Unit WeightsInterval Scheduling Is Fixed-ParameterTractable for the Machines and the LargestProcessing Time
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    Lean source view on GitHub

    1import Lax434175.IsemLink
    2import Lax888481.Theorem2
    3import Lax496464.WH_D12_MulticolouredClique
    4
    5/-!
    6---
    7title: Hardness of P | M_j | Σ w_j Z_j
    8type: theorem
    9---
    10Read through interval scheduling with eligible machine sets (lax-888481), the
    11zoo problem P∣Mj∣∑wjZjP \mid M_j \mid \sum w_j Z_j inherits the two hardness results
    12of that problem.
    13
    14**W[1]-hardness for the number of machines.** Multicoloured Clique,
    15parameterized by the number of colours, fpt-reduces to interval scheduling
    16parameterized by the number of machines (Theorem 1 of lax-888481), and that
    17problem fpt-reduces to P∣Mj∣∑wjZjP \mid M_j \mid \sum w_j Z_j parameterized by the number of
    18machines, by padding. Both reductions are strict fpt-reductions of the
    19archive, computed by word RAM programs in linear fixed-parameter time; they
    20raise the parameter by computable functions of it, and the numbers they write
    21are below 2e(k) (∣x∣+1)2^{e(k)\,(|x|+1)} for a computable ee, where ∣x∣|x| is the bit size
    22of the input and kk its parameter. So both are fpt-reductions in the sense of
    23lax-496464, and so is their composition.
    24
    25**Theorem.** Multicoloured Clique fpt-reduces to
    26P∣Mj∣∑wjZjP \mid M_j \mid \sum w_j Z_j parameterized by the number of machines. Since
    27Multicoloured Clique is W[1]-complete (lax-496464), the problem is W[1]-hard.
    28
    29**NP-hardness for pmax⁡≤25p_{\max} \le 25.** For an interval scheduling instance
    30II, let I′I' be its padding: a job without an eligible machine gets one new
    31machine and weight 00. Read I′I' as an instance of
    32P∣Mj∣∑wjZjP \mid M_j \mid \sum w_j Z_j with threshold ∑jwj′−∑jwj\sum_j w'_j - \sum_j w_j, the
    33total weight of I′I' minus the total weight of II.
    34
    35**Theorem.** Deciding this instance is NP-hard already on the interval
    36scheduling instances with processing times at most 2525 and unit weights: every
    37language in NP reduces to it by a polynomial-time Turing machine writing the
    38encoding of II. On such an instance the threshold is met exactly when every
    39job of II can be scheduled, which is NP-hard by Theorem 2 of lax-888481.
    40Padding keeps the processing times, so the zoo instances have
    41pmax⁡≤25p_{\max} \le 25, and the problem is para-NP-hard for pmax⁡p_{\max}.
    42-/
    43
    44namespace Lax434175.JitHardness
    45open Lax434175 Lax434175.Problems Lax434175.Assembly Lax434175.IsemLink
    46open Lax888481.Scheduling Lax888481.NPHardness
    47open Lax496464.WH_A2_FptReductions Lax496464.WH_B4_Hierarchies
    48
    49axiom mcc_fptReduces_jitByMachines :
    50 Lax888481.MulticolouredClique.problem ≤ᶠᵖᵗ jitByMachines
    51
    52axiom w1Hard_jitByMachines : Hard (W 1) jitByMachines
    53
    54/-- The zoo instance of the padding of `I` meets the threshold: total weight of
    55the padding minus total weight of `I`. -/
    56def JitYes (I : Instance) : Prop :=
    57 (problem _ jitSets).Decides (toZoo (pad I))
    58 (((totalWeight (pad I) : ℤ) - totalWeight I : ℤ) : ℚ)
    59
    60axiom npHardOn_jit_pmax_le :
    61 NPHardOn JitYes fun I => I.pmax ≤ 25 ∧ ∀ j, I.w j = 1
    62
    63end Lax434175.JitHardness
    64
    Show ProofShow ProofShow Proof

    Discussion

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

    Loading discussion…