Theorem 7 — is NP-hard in the strong sense
ProvedResourceScheduling.Chain.p2_res111_chain_stronglyNPHardAssume that 3-PARTITION (with ) 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
the language of unary codes of pairs , where is an instance with two identical machines, a single resource of size one, requirements in , acyclic chain-like precedence constraints and unit-time jobs, and some feasible schedule of has , 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 and .
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.
import Mathlib import Definitions.Def_ResourceScheduling_Chain_Complexity import Definitions.Def_ResourceScheduling_Chain_ThreePartition import Definitions.Def_ResourceScheduling_Chain_Problems
namespace ResourceScheduling.Chain
theorem p2_res111_chain_stronglyNPHard
(h3P : StronglyNPHard ThreePartition.code ThreePartition.IsYes) :
StronglyNPHard Instance.decisionCode P2Res111Chain := by sorry
end ResourceScheduling.Chain
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:
- is a property of a pair: an encoding and a yes-predicate 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.
- and are an encoding of instances and a yes-predicate for a problem named Three-Partition. They come from the imported Three-Partition module.
- is an encoding of instances of a scheduling
Instancetype. 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:
In words: if Three-Partition, under the encoding and yes-predicate , satisfies the property , then the scheduling decision problem, under the encoding and yes-predicate , 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 and the predicate . 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 , as defined, can never hold for , the theorem is vacuously true and says nothing about the scheduling problem. If , as defined, holds trivially for every encoding–predicate pair, the conclusion carries no content. Any such defaults inside or , such as how malformed or empty instances are handled, are decided by those definitions and cannot be seen from this statement.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.