Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3 — Q2 | res·11, p_j = 1 | C_max is NP-hard in the strong sense

Proved
ResourceScheduling.Graph.q2_res11_stronglyNPHard

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

np-hardnessp2o-batch-p100bp2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingstrong-np-hardnessuniform-machines

Assume that PARTITION INTO PATHS OF LENGTH 2 is NP-hard (Garey and Johnson, problem GT13, the NP-completeness result the paper cites as [5]). Then the decision version of

Q2 ∣ res⋅11, pj=1 ∣ Cmax⁡Q2\,|\,res{\cdot}11,\,p_j=1\,|\,C_{\max}Q2∣res⋅11,pj​=1∣Cmax​

is NP-hard in the strong sense: given two uniform machines with positive integer speeds q1,q2q_1,q_2q1​,q2​, nnn unit-time jobs (processing time 1/qi1/q_i1/qi​ on machine MiM_iMi​), lll resources of size 111 (with lll part of the input) and requirements rhj∈{0,1}r_{hj}\in\{0,1\}rhj​∈{0,1}, and a threshold yyy, deciding whether a feasible schedule with Cmax⁡≤yC_{\max}\le yCmax​≤y exists is NP-hard even when all numbers are written in unary.

Two identical machines are polynomially solvable under any resource constraints (Theorem 1); this theorem shows that two machines of different speeds already make the problem hard once the number of unit resources is part of the input.

Formalization Note. The cited NP-hardness of PARTITION INTO PATHS OF LENGTH 2 is the only hypothesis; it concerns the language of codes of yes-instances (unary ttt followed by the adjacency matrix). The speeds range over all positive integers, in either order. Strong NP-hardness is NP-hardness of the language of unary codes of yes-instances, which is equivalent to Garey and Johnson's definition.

Preamble
import Mathlib
import Definitions.Def_ResourceScheduling_Graph_Construction
Formal statement
namespace ResourceScheduling.Graph

/-- Theorem 3, p. 15: `Q2 | res·11, p_j = 1 | C_max` is NP-hard in the strong sense, given that
PARTITION INTO PATHS OF LENGTH 2 is NP-hard (Garey & Johnson 1979, GT13, cited by the paper). -/
theorem q2_res11_stronglyNPHard (hP : NPHard pathsLang) :
    StronglyNPHard Q2Yes encQ2 := by sorry

end ResourceScheduling.Graph
Source
Błażewicz, Lenstra & Rinnooy Kan, Scheduling subject to resource constraints: classification and complexity, Discrete Appl. Math. 5 (1983), p. 15, Theorem 3
Read-back

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

The declaration takes one hypothesis and makes one conclusion. Every symbol it uses (NPHard, pathsLang, StronglyNPHard, Q2Yes, encQ2) comes from the imported module Definitions.Def_ResourceScheduling_Graph_Construction. That module's code is not part of what is shown here, so none of these names can be unfolded. The read-back below reports them only as named objects of that module, inside the namespace ResourceScheduling.Graph. It does not use the attached documentation comment, which describes intent rather than code.

Hypothesis. Assume the property NPHard\mathrm{NPHard}NPHard holds of LpathsL_{\mathrm{paths}}Lpaths​ (pathsLang).

  • NPHard\mathrm{NPHard}NPHard is a predicate defined in the imported module.
  • LpathsL_{\mathrm{paths}}Lpaths​ is an object defined in the imported module. Its name suggests a language (a set of encoded instances), but the code shown does not say what it contains.
  • This is an assumption, not something the declaration proves. The statement is conditional on it.

Conclusion. The two-argument property StronglyNPHard\mathrm{StronglyNPHard}StronglyNPHard holds of the pair

(Q2yes, encQ2),\bigl(Q_2^{\mathrm{yes}},\ \mathrm{enc}_{Q_2}\bigr),(Q2yes​, encQ2​​),

where:

  • Q2yesQ_2^{\mathrm{yes}}Q2yes​ (Q2Yes) is an object defined in the imported module. Its name suggests the set of yes-instances of some decision problem, but the code shown does not say which.
  • encQ2\mathrm{enc}_{Q_2}encQ2​​ (encQ2) is an object defined in the imported module. Its name suggests an encoding of instances.
  • StronglyNPHard\mathrm{StronglyNPHard}StronglyNPHard is a predicate defined in the imported module. Whether it refers to numbers written in unary, to bounds on the numerical values in an instance, or to anything else cannot be read from this code.

In full, the statement says:

NPHard(Lpaths)  ⟹  StronglyNPHard(Q2yes,encQ2).\mathrm{NPHard}(L_{\mathrm{paths}}) \;\Longrightarrow\; \mathrm{StronglyNPHard}\bigl(Q_2^{\mathrm{yes}}, \mathrm{enc}_{Q_2}\bigr).NPHard(Lpaths​)⟹StronglyNPHard(Q2yes​,encQ2​​).

What the code does not show. Nothing here says what scheduling problem, machine model, resource constraint, processing times, objective or graph problem these objects encode. Nothing ties LpathsL_{\mathrm{paths}}Lpaths​ to Q2yesQ_2^{\mathrm{yes}}Q2yes​ or to encQ2\mathrm{enc}_{Q_2}encQ2​​ either. Any such meaning lives entirely in the imported definitions. There are no universally or existentially quantified variables, no type parameters, no typeclass assumptions and no numeric arguments. The only binder is the hypothesis above.

Degenerate cases. The statement has no types, counts, horizons or arithmetic of its own, so it has no empty-type, zero-size, division-by-zero, natural-number subtraction or empty-supremum cases. Any such cases sit inside the imported definitions, which are not shown. What the statement asserts at the edges depends only on how those definitions behave:

  • If NPHard(Lpaths)\mathrm{NPHard}(L_{\mathrm{paths}})NPHard(Lpaths​) is false or unprovable under the imported definitions, the implication is vacuously true and says nothing about Q2yesQ_2^{\mathrm{yes}}Q2yes​.
  • If StronglyNPHard\mathrm{StronglyNPHard}StronglyNPHard holds of this pair trivially (for example, if Q2yesQ_2^{\mathrm{yes}}Q2yes​ or encQ2\mathrm{enc}_{Q_2}encQ2​​ is degenerate, or the predicate is weak), the conclusion holds without using the hypothesis.
  • If NPHard\mathrm{NPHard}NPHard holds of every language, or of none, the hypothesis carries no information.

None of these cases can be ruled in or out from the code shown.

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

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 28, 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