Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Proved
ResourceScheduling.Graph.p3_res11_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 PARTITION INTO TRIANGLES is NP-hard (Garey and Johnson, problem GT11, the NP-completeness result the paper cites as [5]). Then the decision version of

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

is NP-hard in the strong sense: given three identical machines, nnn unit-time jobs, 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.

Together with Theorem 1 (two identical machines are polynomially solvable under any resource constraints), this shows that three identical machines 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 TRIANGLES is the only hypothesis; it concerns the language of codes of yes-instances (unary ttt followed by the adjacency matrix). 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 2, p. 15: `P3 | res·11, p_j = 1 | C_max` is NP-hard in the strong sense, given that
PARTITION INTO TRIANGLES is NP-hard (Garey & Johnson 1979, GT11, cited by the paper). -/
theorem p3_res11_stronglyNPHard (hT : NPHard trianglesLang) :
    StronglyNPHard P3Yes encP3 := 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 2
Read-back

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

This is a conditional statement. Its hypothesis and conclusion both use the notion of NP-hardness from an imported P/NP module. Under that notion, a language LLL is NP-hard if every NP language over every finite nonempty alphabet reduces to LLL by a polynomial-time many-one reduction. The notions of NP and of reduction are the imported ones and are not shown here.

Hypothesis. The following language over {one,sep}\{\mathsf{one},\mathsf{sep}\}{one,sep} is NP-hard: the set of codes of graph instances (t,G)(t, G)(t,G) such that the vertex set {0,…,3t−1}\{0,\dots,3t-1\}{0,…,3t−1} can be split into ttt triples, each forming a triangle in GGG. The code of (t,G)(t, G)(t,G) is onetsep\mathsf{one}^t\mathsf{sep}onetsep followed by the 3t×3t3t\times 3t3t×3t adjacency matrix, row by row, with one\mathsf{one}one for an edge and sep\mathsf{sep}sep otherwise.

Conclusion. The following language over {one,sep}\{\mathsf{one},\mathsf{sep}\}{one,sep} is NP-hard: the set of words enc(x)\mathrm{enc}(x)enc(x) for data records xxx that satisfy the conditions below.

The record xxx consists of:

  • nnn jobs and lll resources;
  • requirements rhj∈{0,1}r_{hj} \in \{0,1\}rhj​∈{0,1};
  • a threshold y∈Ny \in \mathbb Ny∈N.

The condition on xxx is that there is a feasible schedule with Cmax⁡≤yC_{\max} \le yCmax​≤y on three identical machines. In that schedule:

  • every job takes unit time on its machine;
  • start times are nonnegative;
  • distinct jobs on the same machine do not overlap;
  • every resource has size 111, so at each real time at most one executing job requires each resource;
  • there is no precedence.

The encoding is

enc(x)=onensep onelsep ∏h∏jonerhjsep  oneysep,\mathrm{enc}(x) = \mathsf{one}^n\mathsf{sep}\ \mathsf{one}^l\mathsf{sep}\ \prod_{h}\prod_{j}\mathsf{one}^{r_{hj}}\mathsf{sep}\ \ \mathsf{one}^y\mathsf{sep},enc(x)=onensep onelsep h∏​j∏​onerhj​sep  oneysep,

with the requirements listed resource by resource.

Degenerate case. The theorem does not assert that either language is NP-hard outright. If the hypothesis fails, the statement says nothing.

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