Theorem 2 — P3 | res·11, p_j = 1 | C_max is NP-hard in the strong sense
ProvedResourceScheduling.Graph.p3_res11_stronglyNPHardAssume 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
is NP-hard in the strong sense: given three identical machines, unit-time jobs, resources of size (with part of the input) and requirements , and a threshold , deciding whether a feasible schedule with 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 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.
import Mathlib import Definitions.Def_ResourceScheduling_Graph_Construction
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
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 is NP-hard if every NP language over every finite nonempty alphabet reduces to 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 is NP-hard: the set of codes of graph instances such that the vertex set can be split into triples, each forming a triangle in . The code of is followed by the adjacency matrix, row by row, with for an edge and otherwise.
Conclusion. The following language over is NP-hard: the set of words for data records that satisfy the conditions below.
The record consists of:
- jobs and resources;
- requirements ;
- a threshold .
The condition on is that there is a feasible schedule with 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 , so at each real time at most one executing job requires each resource;
- there is no precedence.
The encoding is
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.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.