Knapsack, in binary
Lax799700.Knapsack · concepts/Lax799700/Knapsack.lean · lax-799700
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural 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 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
Evidence
Lean source view on GitHub
| 1 | import Mathlib.Algebra.BigOperators.Finprod |
| 2 | import Mathlib.ModelTheory.Semantics |
| 3 | import Mathlib.ModelTheory.Complexity |
| 4 | import Mathlib.Tactic.FinCases |
| 5 | import Mathlib.Data.Set.Finite.Lemmas |
| 6 | import Mathlib.Data.Fintype.EquivFin |
| 7 | import Mathlib.Data.Set.Card |
| 8 | import Mathlib.SetTheory.Cardinal.Finite |
| 9 | import Mathlib.Logic.Equiv.Prod |
| 10 | import Mathlib.ModelTheory.Syntax |
| 11 | import Lax799700.Common |
| 12 | import Lax904597.Machines |
| 13 | import Lax904597.Classes |
| 14 | import Lax799700.Problems |
| 15 | |
| 16 | /-! |
| 17 | --- |
| 18 | title: Knapsack, in binary |
| 19 | type: theorem |
| 20 | --- |
| 21 | KNAPSACK, in the subset-sum form of Karp: given weights and a target, is |
| 22 | there a set of items whose weights sum to the target? Numbers are |
| 23 | written in binary, as the last four problems of Karp's list require: |
| 24 | under the unary encoding they are solvable in polynomial time by dynamic |
| 25 | programming, so the representation is part of the statement. The |
| 26 | vocabulary carries the items, the bit positions, the bits of each |
| 27 | weight, the bits of the target, and a linear order fixing the place |
| 28 | values; being a linear order is folded into the yes-instances. The |
| 29 | decoding (binNum) sums over a set of positions, and |
| 30 | is defined for an arbitrary relation so that invariance is a plain |
| 31 | transport. Membership is by an existential second-order definition that |
| 32 | walks the order on items to verify the arithmetic; hardness is an |
| 33 | ordered first-order reduction from Exact Cover. |
| 34 | |
| 35 | -/ |
| 36 | |
| 37 | namespace Lax799700.Knapsack |
| 38 | |
| 39 | open Lax799700.Common Lax904597.Machines |
| 40 | |
| 41 | open FirstOrder |
| 42 | |
| 43 | open FirstOrder.Language |
| 44 | |
| 45 | /-- The relation symbols of the language. -/ |
| 46 | inductive 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 |
| 60 | positions, the bits of each item's weight and of the target, and a linear |
| 61 | order. -/ |
| 62 | def binWeights : FirstOrder.Language := |
| 63 | ⟨fun _ => Empty, binWeightsRel⟩ |
| 64 | |
| 65 | instance instIsRelationalBinWeights : FirstOrder.Language.IsRelational binWeights := fun _ => |
| 66 | (inferInstance : IsEmpty Empty) |
| 67 | |
| 68 | /-- `item i`: `i` is an item. -/ |
| 69 | abbrev bwItem : binWeights.Relations 1 := |
| 70 | .item |
| 71 | |
| 72 | /-- `posn p`: `p` is a bit position. -/ |
| 73 | abbrev bwPosn : binWeights.Relations 1 := |
| 74 | .posn |
| 75 | |
| 76 | /-- `bit i p`: the weight of `i` has bit 1 at position `p`. -/ |
| 77 | abbrev bwBit : binWeights.Relations 2 := |
| 78 | .bit |
| 79 | |
| 80 | /-- `tgt p`: the target has bit 1 at position `p`. -/ |
| 81 | abbrev bwTgt : binWeights.Relations 1 := |
| 82 | .tgt |
| 83 | |
| 84 | /-- `le a b`: the linear order carrying the place values. -/ |
| 85 | abbrev bwLe : binWeights.Relations 2 := |
| 86 | .le |
| 87 | |
| 88 | open FirstOrder |
| 89 | |
| 90 | open Language Structure |
| 91 | |
| 92 | section Shorthands |
| 93 | |
| 94 | variable {A : Type} [binWeights.Structure A] |
| 95 | |
| 96 | /-- `item i`: `i` is an item. -/ |
| 97 | def 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. -/ |
| 101 | def 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`. -/ |
| 105 | def 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`. -/ |
| 109 | def 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. -/ |
| 113 | def 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. -/ |
| 117 | noncomputable def BWWeight (i : A) : ℕ := binNum BWLe BWPosn (BWBit i) |
| 118 | |
| 119 | end Shorthands |
| 120 | |
| 121 | /-- The target of a binary-weighted instance, decoded. -/ |
| 122 | noncomputable def BWTarget (A : Type) [binWeights.Structure A] : ℕ := |
| 123 | binNum (BWLe (A := A)) BWPosn BWTgt |
| 124 | |
| 125 | section Problem |
| 126 | |
| 127 | variable (A : Type) [binWeights.Structure A] |
| 128 | |
| 129 | /-- A binary-weighted instance is a yes-instance of Knapsack when its order is |
| 130 | a linear order and some set of items has weights summing exactly to the |
| 131 | target. (Karp's KNAPSACK is this subset-sum question.) -/ |
| 132 | def 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 | |
| 137 | end Problem |
| 138 | |
| 139 | open Lax904597.Problems Lax904597.Classes Lax799700.Problems |
| 140 | |
| 141 | /-- The property `HasSubsetSum` is isomorphism-invariant. -/ |
| 142 | axiom 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`? -/ |
| 146 | def Knapsack : DecisionProblem Lax799700.Knapsack.binWeights := |
| 147 | DecisionProblem.ofPred HasSubsetSum |
| 148 | |
| 149 | /-- The yes-instances of Knapsack are exactly the structures satisfying |
| 150 | `HasSubsetSum`. -/ |
| 151 | axiom knapsack_iff : ∀ (A : Type) [Lax799700.Knapsack.binWeights.Structure A], Knapsack A ↔ HasSubsetSum A |
| 152 | |
| 153 | /-- Knapsack is NP-complete. -/ |
| 154 | axiom knapsack_NP_complete : NP.Complete Knapsack |
| 155 | |
| 156 | end Lax799700.Knapsack |
| 157 |
Used by
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments