Knapsack, in binary

Lax799700.Knapsack · concepts/Lax799700/Knapsack.lean · lax-799700

proven

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

    Theorem

    KNAPSACK, in the subset-sum form of Karp: given weights and a target, is there a set of items whose weights sum to the target? Numbers are written in binary, as the last four problems of Karp's list require: under the unary encoding they are solvable in polynomial time by dynamic programming, so the representation is part of the statement. The vocabulary carries the items, the bit positions, the bits of each weight, the bits of the target, and a linear order fixing the place values; being a linear order is folded into the yes-instances. The decoding (binNum) sums 2rank2^{\mathrm{rank}} over a set of positions, and is defined for an arbitrary relation so that invariance is a plain transport. Membership is by an existential second-order definition that walks the order on items to verify the arithmetic; hardness is an ordered first-order reduction from Exact Cover.

    Concept map
    10 concepts; 1 descendant hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    This concept declares 3 statements. Each proof establishes one of them relative to its assumptions.

    Lean source view on GitHub

    1import Mathlib.Algebra.BigOperators.Finprod
    2import Mathlib.ModelTheory.Semantics
    3import Mathlib.ModelTheory.Complexity
    4import Mathlib.Tactic.FinCases
    5import Mathlib.Data.Set.Finite.Lemmas
    6import Mathlib.Data.Fintype.EquivFin
    7import Mathlib.Data.Set.Card
    8import Mathlib.SetTheory.Cardinal.Finite
    9import Mathlib.Logic.Equiv.Prod
    10import Mathlib.ModelTheory.Syntax
    11import Lax799700.Common
    12import Lax904597.Machines
    13import Lax904597.Classes
    14import Lax799700.Problems
    15
    16/-!
    17---
    18title: Knapsack, in binary
    19type: theorem
    20---
    21KNAPSACK, in the subset-sum form of Karp: given weights and a target, is
    22there a set of items whose weights sum to the target? Numbers are
    23written in binary, as the last four problems of Karp's list require:
    24under the unary encoding they are solvable in polynomial time by dynamic
    25programming, so the representation is part of the statement. The
    26vocabulary carries the items, the bit positions, the bits of each
    27weight, the bits of the target, and a linear order fixing the place
    28values; being a linear order is folded into the yes-instances. The
    29decoding (binNum) sums 2rank2^{\mathrm{rank}} over a set of positions, and
    30is defined for an arbitrary relation so that invariance is a plain
    31transport. Membership is by an existential second-order definition that
    32walks the order on items to verify the arithmetic; hardness is an
    33ordered first-order reduction from Exact Cover.
    34
    35-/
    36
    37namespace Lax799700.Knapsack
    38
    39open Lax799700.Common Lax904597.Machines
    40
    41open FirstOrder
    42
    43open FirstOrder.Language
    44
    45/-- The relation symbols of the language. -/
    46inductive binWeightsRel : ℕ → Type where
    47/-- `item i`: `i` is an item. -/
    48 | item : binWeightsRel 1
    49/-- `posn p`: `p` is a bit position. -/
    50 | posn : binWeightsRel 1
    51/-- `bit i p`: the weight of `i` has bit 1 at position `p`. -/
    52 | bit : binWeightsRel 2
    53/-- `tgt p`: the target has bit 1 at position `p`. -/
    54 | tgt : binWeightsRel 1
    55/-- `le a b`: the linear order carrying the place values. -/
    56 | le : binWeightsRel 2
    57 deriving DecidableEq
    58
    59/-- The relational language of binary-weighted instances: items and bit
    60positions, the bits of each item's weight and of the target, and a linear
    61order. -/
    62def binWeights : FirstOrder.Language :=
    63 ⟨fun _ => Empty, binWeightsRel⟩
    64
    65instance instIsRelationalBinWeights : FirstOrder.Language.IsRelational binWeights := fun _ =>
    66 (inferInstance : IsEmpty Empty)
    67
    68/-- `item i`: `i` is an item. -/
    69abbrev bwItem : binWeights.Relations 1 :=
    70 .item
    71
    72/-- `posn p`: `p` is a bit position. -/
    73abbrev bwPosn : binWeights.Relations 1 :=
    74 .posn
    75
    76/-- `bit i p`: the weight of `i` has bit 1 at position `p`. -/
    77abbrev bwBit : binWeights.Relations 2 :=
    78 .bit
    79
    80/-- `tgt p`: the target has bit 1 at position `p`. -/
    81abbrev bwTgt : binWeights.Relations 1 :=
    82 .tgt
    83
    84/-- `le a b`: the linear order carrying the place values. -/
    85abbrev bwLe : binWeights.Relations 2 :=
    86 .le
    87
    88open FirstOrder
    89
    90open Language Structure
    91
    92section Shorthands
    93
    94variable {A : Type} [binWeights.Structure A]
    95
    96/-- `item i`: `i` is an item. -/
    97def BWItem {A : Type} [binWeights.Structure A] (a0 : A) : Prop :=
    98 FirstOrder.Language.Structure.RelMap bwItem ![a0]
    99
    100/-- `posn p`: `p` is a bit position. -/
    101def BWPosn {A : Type} [binWeights.Structure A] (a0 : A) : Prop :=
    102 FirstOrder.Language.Structure.RelMap bwPosn ![a0]
    103
    104/-- `bit i p`: the weight of `i` has bit 1 at position `p`. -/
    105def BWBit {A : Type} [binWeights.Structure A] (a0 : A) (a1 : A) : Prop :=
    106 FirstOrder.Language.Structure.RelMap bwBit ![a0, a1]
    107
    108/-- `tgt p`: the target has bit 1 at position `p`. -/
    109def BWTgt {A : Type} [binWeights.Structure A] (a0 : A) : Prop :=
    110 FirstOrder.Language.Structure.RelMap bwTgt ![a0]
    111
    112/-- `le a b`: the linear order carrying the place values. -/
    113def BWLe {A : Type} [binWeights.Structure A] (a0 : A) (a1 : A) : Prop :=
    114 FirstOrder.Language.Structure.RelMap bwLe ![a0, a1]
    115
    116/-- The weight of an item, decoded. -/
    117noncomputable def BWWeight (i : A) : ℕ := binNum BWLe BWPosn (BWBit i)
    118
    119end Shorthands
    120
    121/-- The target of a binary-weighted instance, decoded. -/
    122noncomputable def BWTarget (A : Type) [binWeights.Structure A] : ℕ :=
    123 binNum (BWLe (A := A)) BWPosn BWTgt
    124
    125section Problem
    126
    127variable (A : Type) [binWeights.Structure A]
    128
    129/-- A binary-weighted instance is a yes-instance of Knapsack when its order is
    130a linear order and some set of items has weights summing exactly to the
    131target. (Karp's KNAPSACK is this subset-sum question.) -/
    132def HasSubsetSum : Prop :=
    133 Finite A ∧ IsLinOrd (BWLe (A := A)) ∧
    134 ∃ S : A → Prop, (∀ i, S i → BWItem i) ∧
    135 (∑ᶠ i ∈ {i | S i}, BWWeight i) = BWTarget A
    136
    137end Problem
    138
    139open Lax904597.Problems Lax904597.Classes Lax799700.Problems
    140
    141/-- The property `HasSubsetSum` is isomorphism-invariant. -/
    142axiom hasSubsetSum_iso : ∀ {A B : Type} [Lax799700.Knapsack.binWeights.Structure A] [Lax799700.Knapsack.binWeights.Structure B],
    143 (A ≃[Lax799700.Knapsack.binWeights] B) → (HasSubsetSum A ↔ HasSubsetSum B)
    144
    145/-- The problem Knapsack: does the structure satisfy `HasSubsetSum`? -/
    146def Knapsack : DecisionProblem Lax799700.Knapsack.binWeights :=
    147 DecisionProblem.ofPred HasSubsetSum
    148
    149/-- The yes-instances of Knapsack are exactly the structures satisfying
    150`HasSubsetSum`. -/
    151axiom knapsack_iff : ∀ (A : Type) [Lax799700.Knapsack.binWeights.Structure A], Knapsack A ↔ HasSubsetSum A
    152
    153/-- Knapsack is NP-complete. -/
    154axiom knapsack_NP_complete : NP.Complete Knapsack
    155
    156end Lax799700.Knapsack
    157
    Show ProofShow ProofShow Proof

    Discussion

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

    Loading discussion…