NP-Hardness, and Strong NP-Hardness, of a Scheduling Problem

Lax496464.NPHardness · concepts/Lax496464/NPHardness.lean · lax-496464

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural 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 P=NP\mathrm{P} = \mathrm{NP}: 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
    6 concepts; 1 descendant hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    In the paper

    • page 7 of this submission's paper

    Lean source view on GitHub

    1import Lax496464.BinaryEncoding
    2import Lax434930.NondeterministicPolynomialTime
    3
    4/-!
    5---
    6title: NP-Hardness, and Strong NP-Hardness, of a Scheduling Problem
    7type: definition
    8---
    9A property of instances is *NP-hard* if every language in NP has a polynomial-time
    10many-one reduction to it, the reduction's output being an instance in the binary
    11encoding.
    12
    13It is *strongly NP-hard* if such a reduction exists whose emitted instances have all
    14their numbers bounded by a fixed polynomial in the length of the input. A strongly
    15NP-hard problem admits no pseudo-polynomial algorithm unless P=NP\mathrm{P} = \mathrm{NP}
    16: an algorithm polynomial in the magnitudes of the numbers would be
    17polynomial in the input length on the image of such a reduction.
    18
    19# Formalization Notes
    20
    21Hardness is defined by quantifying over NP rather than against a fixed complete problem.
    22NP is available, so the definition a textbook gives can be written down.
    23
    24The reduction's target is an instance with its threshold rather than a word, with the
    25encoding applied by the definition. This keeps a statement about a problem from also
    26being 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
    29single reduction witnesses both the plain claim and the claim on the slice the
    30construction actually lands in — here, instances all of whose weights are one.
    31
    32Strength is a clause on the reduction, not a different encoding. The usual formulation —
    33NP-hardness under the unary encoding — says the same thing: a polynomial-time reduction
    34writing numbers in unary is exactly a polynomial-time reduction whose numbers are
    35polynomially bounded. Stating it as a bound keeps one encoding in play and makes the
    36content visible, namely that the construction's numbers do not grow with the values it
    37reads but only with the size of what it reads.
    38
    39The polynomial is written as (∣x∣+1)c(|x|+1)^c rather than as an element of N[X]\mathbb{N}[X].
    40Every polynomial with natural coefficients is dominated by such a power, so nothing is
    41lost, and the bound stays elementary, in the style of the running times on the word RAM.
    42-/
    43
    44namespace Lax496464.NPHardness
    45
    46open Lax496464.FlowShop Lax496464.BinaryEncoding
    47open Lax434930.PolynomialTime Lax434930.NondeterministicPolynomialTime
    48
    49/-- A decision problem on instances with a threshold. -/
    50abbrev Problem := Instance → ℕ → Prop
    51
    52/-- `Q` is **NP-hard**: every language in NP reduces to it in polynomial time. -/
    53def 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
    61have all their numbers, and their threshold, bounded by a fixed polynomial in the length
    62of the input. -/
    63def 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
    72lie in `C`. -/
    73def 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
    82end 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 (∣x∣+1)c(|x|+1)^c rather than as an element of N[X]\mathbb{N}[X]. 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.

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…