NP-Hardness, and Strong NP-Hardness, of a Scheduling Problem
Lax496464.NPHardness · concepts/Lax496464/NPHardness.lean · lax-496464
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
A property of instances is NP-hard if every language in NP has a polynomial-time many-one reduction to it, the reduction's output being an instance in the binary encoding.
It is strongly NP-hard if such a reduction exists whose emitted instances have all their numbers bounded by a fixed polynomial in the length of the input. A strongly NP-hard problem admits no pseudo-polynomial algorithm unless : an algorithm polynomial in the magnitudes of the numbers would be polynomial in the input length on the image of such a reduction.
Concept map
In the paper
- page 7 of this submission's paper
Lean source view on GitHub
| 1 | import Lax496464.BinaryEncoding |
| 2 | import Lax434930.NondeterministicPolynomialTime |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: NP-Hardness, and Strong NP-Hardness, of a Scheduling Problem |
| 7 | type: definition |
| 8 | --- |
| 9 | A property of instances is *NP-hard* if every language in NP has a polynomial-time |
| 10 | many-one reduction to it, the reduction's output being an instance in the binary |
| 11 | encoding. |
| 12 | |
| 13 | It is *strongly NP-hard* if such a reduction exists whose emitted instances have all |
| 14 | their numbers bounded by a fixed polynomial in the length of the input. A strongly |
| 15 | NP-hard problem admits no pseudo-polynomial algorithm unless |
| 16 | : an algorithm polynomial in the magnitudes of the numbers would be |
| 17 | polynomial in the input length on the image of such a reduction. |
| 18 | |
| 19 | # Formalization Notes |
| 20 | |
| 21 | Hardness is defined by quantifying over NP rather than against a fixed complete problem. |
| 22 | NP is available, so the definition a textbook gives can be written down. |
| 23 | |
| 24 | The reduction's target is an instance with its threshold rather than a word, with the |
| 25 | encoding applied by the definition. This keeps a statement about a problem from also |
| 26 | being a statement about which words are well-formed. |
| 27 | |
| 28 | "Strongly NP-hard on a class" is the same definition with one further clause, so that a |
| 29 | single reduction witnesses both the plain claim and the claim on the slice the |
| 30 | construction actually lands in — here, instances all of whose weights are one. |
| 31 | |
| 32 | Strength is a clause on the reduction, not a different encoding. The usual formulation — |
| 33 | NP-hardness under the unary encoding — says the same thing: a polynomial-time reduction |
| 34 | writing numbers in unary is exactly a polynomial-time reduction whose numbers are |
| 35 | polynomially bounded. Stating it as a bound keeps one encoding in play and makes the |
| 36 | content visible, namely that the construction's numbers do not grow with the values it |
| 37 | reads but only with the size of what it reads. |
| 38 | |
| 39 | The polynomial is written as rather than as an element of . |
| 40 | Every polynomial with natural coefficients is dominated by such a power, so nothing is |
| 41 | lost, and the bound stays elementary, in the style of the running times on the word RAM. |
| 42 | -/ |
| 43 | |
| 44 | namespace Lax496464.NPHardness |
| 45 | |
| 46 | open Lax496464.FlowShop Lax496464.BinaryEncoding |
| 47 | open Lax434930.PolynomialTime Lax434930.NondeterministicPolynomialTime |
| 48 | |
| 49 | /-- A decision problem on instances with a threshold. -/ |
| 50 | abbrev Problem := Instance → ℕ → Prop |
| 51 | |
| 52 | /-- `Q` is **NP-hard**: every language in NP reduces to it in polynomial time. -/ |
| 53 | def NPHard (Q : Problem) : Prop := |
| 54 | ∀ A : Language, A ∈ NP → |
| 55 | ∃ f : Word → Instance × ℕ, |
| 56 | Nonempty (Turing.TM2ComputableInPolyTime id |
| 57 | (fun z : Instance × ℕ => encodeDecisionInstance z.1 z.2) f) ∧ |
| 58 | ∀ x, x ∈ A ↔ Q (f x).1 (f x).2 |
| 59 | |
| 60 | /-- `Q` is **strongly NP-hard**: it is NP-hard by a reduction whose emitted instances |
| 61 | have all their numbers, and their threshold, bounded by a fixed polynomial in the length |
| 62 | of the input. -/ |
| 63 | def StronglyNPHard (Q : Problem) : Prop := |
| 64 | ∀ A : Language, A ∈ NP → |
| 65 | ∃ (f : Word → Instance × ℕ) (c : ℕ), |
| 66 | Nonempty (Turing.TM2ComputableInPolyTime id |
| 67 | (fun z : Instance × ℕ => encodeDecisionInstance z.1 z.2) f) ∧ |
| 68 | (∀ x, max (maxNumber (f x).1) (f x).2 ≤ (x.length + 2) ^ c) ∧ |
| 69 | ∀ x, x ∈ A ↔ Q (f x).1 (f x).2 |
| 70 | |
| 71 | /-- `Q` is **strongly NP-hard on `C`**: the same, by a reduction all of whose outputs |
| 72 | lie in `C`. -/ |
| 73 | def StronglyNPHardOn (Q : Problem) (C : Instance → Prop) : Prop := |
| 74 | ∀ A : Language, A ∈ NP → |
| 75 | ∃ (f : Word → Instance × ℕ) (c : ℕ), |
| 76 | Nonempty (Turing.TM2ComputableInPolyTime id |
| 77 | (fun z : Instance × ℕ => encodeDecisionInstance z.1 z.2) f) ∧ |
| 78 | (∀ x, max (maxNumber (f x).1) (f x).2 ≤ (x.length + 2) ^ c) ∧ |
| 79 | (∀ x, C (f x).1) ∧ |
| 80 | ∀ x, x ∈ A ↔ Q (f x).1 (f x).2 |
| 81 | |
| 82 | end Lax496464.NPHardness |
| 83 |
Formalization Notes
Hardness is defined by quantifying over NP rather than against a fixed complete problem. NP is available, so the definition a textbook gives can be written down.
The reduction's target is an instance with its threshold rather than a word, with the encoding applied by the definition. This keeps a statement about a problem from also being a statement about which words are well-formed.
"Strongly NP-hard on a class" is the same definition with one further clause, so that a single reduction witnesses both the plain claim and the claim on the slice the construction actually lands in — here, instances all of whose weights are one.
Strength is a clause on the reduction, not a different encoding. The usual formulation — NP-hardness under the unary encoding — says the same thing: a polynomial-time reduction writing numbers in unary is exactly a polynomial-time reduction whose numbers are polynomially bounded. Stating it as a bound keeps one encoding in play and makes the content visible, namely that the construction's numbers do not grow with the values it reads but only with the size of what it reads.
The polynomial is written as rather than as an element of . Every polynomial with natural coefficients is dominated by such a power, so nothing is lost, and the bound stays elementary, in the style of the running times on the word RAM.
Used by
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments