Theorem 3 — Q2 | res·11, p_j = 1 | C_max is NP-hard in the strong sense
ProvedResourceScheduling.Graph.q2_res11_stronglyNPHardAssume 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
is NP-hard in the strong sense: given two uniform machines with positive integer speeds , unit-time jobs (processing time on machine ), 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.
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 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.
import Mathlib import Definitions.Def_ResourceScheduling_Graph_Construction
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
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 holds of (pathsLang).
- is a predicate defined in the imported module.
- 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 holds of the pair
where:
- (
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) is an object defined in the imported module. Its name suggests an encoding of instances. - 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:
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 to or to 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 is false or unprovable under the imported definitions, the implication is vacuously true and says nothing about .
- If holds of this pair trivially (for example, if or is degenerate, or the predicate is weak), the conclusion holds without using the hypothesis.
- If 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.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.