Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 7 — P2∣res111,chain,pj=1∣Cmax⁡P2\mid res111, chain, p_j=1\mid C_{\max}P2∣res111,chain,pj​=1∣Cmax​ is NP-hard in the strong sense

Proved
ResourceScheduling.Chain.p2_res111_chain_stronglyNPHard

by mikedeng1 · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

np-hardnessp2o-batch-p100bp2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingstrong-np-hardness

Assume that 3-PARTITION (with 14b<aj<12b\tfrac14 b < a_j < \tfrac12 b41​b<aj​<21​b) is NP-hard in the strong sense, i.e. that its language of yes-instances with all numbers written in unary is NP-hard. This is Garey and Johnson's theorem, cited by the paper. Then

P2∣res111, chain, pj=1∣Cmax⁡ is NP-hard in the strong sense:P2\mid res111,\ chain,\ p_j = 1\mid C_{\max} \text{ is NP-hard in the strong sense:}P2∣res111, chain, pj​=1∣Cmax​ is NP-hard in the strong sense:

the language of unary codes of pairs (I,y)(I, y)(I,y), where III is an instance with two identical machines, a single resource of size one, requirements in {0,1}\{0,1\}{0,1}, acyclic chain-like precedence constraints and unit-time jobs, and some feasible schedule of III has Cmax⁡≤yC_{\max} \le yCmax​≤y, is NP-hard.

This is the main theorem of the paper. Two identical machines with unit-time jobs are solvable in polynomial time under any resource constraints when there are no precedence constraints (Theorem 1 of the paper); the theorem shows that one unit resource together with chains already makes the problem strongly NP-hard. It dominates the earlier strong NP-hardness results for P2∣res1⋅⋅,tree,pj=1∣Cmax⁡P2\mid res1\cdot\cdot, tree, p_j=1\mid C_{\max}P2∣res1⋅⋅,tree,pj​=1∣Cmax​ and P2∣res111,prec,pj=1∣Cmax⁡P2\mid res111, prec, p_j=1\mid C_{\max}P2∣res111,prec,pj​=1∣Cmax​.

Formalization Note. The hypothesis is the cited NP-hardness of the source problem, the only fact taken from outside the paper; the reduction and its polynomial running time are what a proof must supply. NP-hardness is with respect to polynomial-time many-one reductions computed by Cook's one-tape Turing machines (CookPvsNP_defs). Schedules have real start times and the resource is checked at every real time. Thresholds are natural numbers, which makes the hardness statement stronger.

Preamble
import Mathlib
import Definitions.Def_ResourceScheduling_Chain_Complexity
import Definitions.Def_ResourceScheduling_Chain_ThreePartition
import Definitions.Def_ResourceScheduling_Chain_Problems
Formal statement
namespace ResourceScheduling.Chain
theorem p2_res111_chain_stronglyNPHard
    (h3P : StronglyNPHard ThreePartition.code ThreePartition.IsYes) :
    StronglyNPHard Instance.decisionCode P2Res111Chain := by sorry
end ResourceScheduling.Chain
Source
Błażewicz, Lenstra & Rinnooy Kan, Scheduling subject to resource constraints: classification and complexity, Discrete Appl. Math. 5 (1983), p. 18, Theorem 7
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

The statement is set in the namespace of chain-structured resource scheduling. It uses four objects that come from imported definition modules. Their definitions are not shown in the code, so this read-back identifies them only by name and by how they are used:

  • StronglyNPHard(c,P)\mathrm{StronglyNPHard}(c, P)StronglyNPHard(c,P) is a property of a pair: an encoding ccc and a yes-predicate PPP on instances. The code calls it "strongly NP-hard", but what that property actually requires is fixed by its definition in the imported complexity module, which is not reproduced here.
  • code3P\mathrm{code}_{3\mathrm{P}}code3P​ and IsYes3P\mathrm{IsYes}_{3\mathrm{P}}IsYes3P​ are an encoding of instances and a yes-predicate for a problem named Three-Partition. They come from the imported Three-Partition module.
  • decisionCode\mathrm{decisionCode}decisionCode is an encoding of instances of a scheduling Instance type. P2Res111Chain\mathrm{P2Res111Chain}P2Res111Chain is a yes-predicate on those instances. Its name suggests a two-machine problem with resource parameters "1 1 1" and chain precedence constraints, but its meaning is whatever the imported problems module defines.

The theorem takes one hypothesis and has no other variables, quantifiers or typeclass assumptions. It states:

StronglyNPHard(code3P, IsYes3P)  ⟹  StronglyNPHard(decisionCode, P2Res111Chain).\mathrm{StronglyNPHard}\big(\mathrm{code}_{3\mathrm{P}},\ \mathrm{IsYes}_{3\mathrm{P}}\big) \;\Longrightarrow\; \mathrm{StronglyNPHard}\big(\mathrm{decisionCode},\ \mathrm{P2Res111Chain}\big).StronglyNPHard(code3P​, IsYes3P​)⟹StronglyNPHard(decisionCode, P2Res111Chain).

In words: if Three-Partition, under the encoding code3P\mathrm{code}_{3\mathrm{P}}code3P​ and yes-predicate IsYes3P\mathrm{IsYes}_{3\mathrm{P}}IsYes3P​, satisfies the property StronglyNPHard\mathrm{StronglyNPHard}StronglyNPHard, then the scheduling decision problem, under the encoding decisionCode\mathrm{decisionCode}decisionCode and yes-predicate P2Res111Chain\mathrm{P2Res111Chain}P2Res111Chain, satisfies the same property.

  • It is only an implication. It does not claim that Three-Partition is strongly NP-hard. That is an assumption the theorem takes as given.
  • It is not unconditional. The theorem does not claim on its own that the scheduling problem is strongly NP-hard.
  • The conclusion depends on the chosen encoding. It concerns only the encoding decisionCode\mathrm{decisionCode}decisionCode and the predicate P2Res111Chain\mathrm{P2Res111Chain}P2Res111Chain. It says nothing about other encodings of the same problem.

The statement has no numeric parameters, horizons or index types, so at this level there are no zero counts, empty types or total-function defaults (division by zero, subtraction in ℕ and so on) to report. The degenerate cases come from the undisplayed definitions. If StronglyNPHard\mathrm{StronglyNPHard}StronglyNPHard, as defined, can never hold for (code3P,IsYes3P)(\mathrm{code}_{3\mathrm{P}}, \mathrm{IsYes}_{3\mathrm{P}})(code3P​,IsYes3P​), the theorem is vacuously true and says nothing about the scheduling problem. If StronglyNPHard\mathrm{StronglyNPHard}StronglyNPHard, as defined, holds trivially for every encoding–predicate pair, the conclusion carries no content. Any such defaults inside P2Res111Chain\mathrm{P2Res111Chain}P2Res111Chain or decisionCode\mathrm{decisionCode}decisionCode, such as how malformed or empty instances are handled, are decided by those definitions and cannot be seen from this statement.

Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me