Documentation

DescriptiveComplexity.Problems.Knapsack.Hardness

Knapsack is NP-hard #

The reduction is Karp's, from EXACT COVER: give the set s the weight ∑_{e ∈ s} B ^ rank e, one digit block per ground element, and give the target the digit 1 in every block. A subfamily then has the right weight exactly when it covers every element once – provided that the digits never carry, which is what choosing the base B above the number of sets buys.

The gadget, in the shape an interpretation can build #

The base is B = 2 ^ |A|, so a block is |A| bit positions, and the bit positions are pairs: the position (e, x) is the x-th bit of the block of the ground element e. The order on positions is lexicographic, so the block of e is a contiguous range of |A| positions and the rank of its lowest position is |A| * rank e (DescriptiveComplexity.KnapRed.bitRank_kLow) – place value (2 ^ |A|) ^ rank e, as wanted.

Only the lowest position of a block ever carries a bit: the weight of s has a 1 at (e, ⊥) for e ∈ s, and the target has a 1 at (e, ⊥) for every e. The digit of the block of e in the sum over a subfamily G is therefore the number of sets of G containing e, at most the number of sets, hence at most |A| < 2 ^ |A| = B. Uniqueness of base-B expansions (DescriptiveComplexity.digitNum_inj) turns the equation into “every digit is 1”, which is exactly exactness of the cover.

The order is needed twice – to say “the lowest position of a block” and to pin the padding of the items down to a single representative – so this is an DescriptiveComplexity.OrderedFOReduction, and being one has the pleasant side effect of supplying the finiteness that the counting needs.

Formula builders over the ordered expansion of set systems #

@[reducible, inline]

The ordered expansion of the language of set systems.

Equations
Instances For
    @[reducible, inline]

    The ground-element symbol in the ordered expansion.

    Equations
    Instances For
      @[reducible, inline]

      The family symbol in the ordered expansion.

      Equations
      Instances For
        @[reducible, inline]

        The incidence symbol in the ordered expansion.

        Equations
        Instances For
          noncomputable def DescriptiveComplexity.KnapRed.minF {α : Type} (x : α) :

          x holds a minimum of the order, as a formula.

          Equations
          Instances For
            @[simp]
            theorem DescriptiveComplexity.KnapRed.realize_memF {α A : Type} [FirstOrder.Language.setSystem.Structure A] [LinearOrder A] {v : α → A} {x f : α} :
            (memF x f).Realize v ↔ SSMem (v x) (v f)
            @[simp]
            theorem DescriptiveComplexity.KnapRed.realize_leF {α A : Type} [FirstOrder.Language.setSystem.Structure A] [LinearOrder A] {v : α → A} {x y : α} :
            (leF x y).Realize v ↔ v x ≤ v y
            @[simp]
            theorem DescriptiveComplexity.KnapRed.realize_eqF {α A : Type} [FirstOrder.Language.setSystem.Structure A] [LinearOrder A] {v : α → A} {x y : α} :
            (eqF x y).Realize v ↔ v x = v y
            @[simp]
            theorem DescriptiveComplexity.KnapRed.realize_ltF {α A : Type} [FirstOrder.Language.setSystem.Structure A] [LinearOrder A] {v : α → A} {x y : α} :
            (ltF x y).Realize v ↔ v x < v y

            Lexicographic order on pairs #

            The lexicographic order on pairs of elements, as the interpretation sees them: coordinates of a 2-tuple.

            Equations
            Instances For

              The interpretation #

              Tags of the reduction: the items (one per set of the family) and the bit positions (one per pair “ground element, index inside its block”).

              • itm : KTag

                The item of a set of the family.

              • pos : KTag

                A bit position.

              Instances For
                @[instance_reducible]
                Equations
                • One or more equations did not get rendered due to their size.

                Defining formula for the bits of the weights: the weight of the set s has a 1 at the lowest position of the block of e exactly when e ∈ s.

                Equations
                Instances For

                  The lexicographic comparison of the two argument tuples, as a formula.

                  Equations
                  Instances For

                    The interpretation of a binary-weighted instance in a set system: one item per set, one bit position per pair “ground element, index”.

                    Equations
                    • One or more equations did not get rendered due to their size.
                    Instances For

                      The points of the interpreted structure #

                      def DescriptiveComplexity.KnapRed.kPt {A : Type} (t : KTag) (w : Fin 2 → A) :

                      The point of tag t over the pair w.

                      Equations
                      Instances For
                        @[simp]
                        theorem DescriptiveComplexity.KnapRed.kPt_snd {A : Type} (t : KTag) (w : Fin 2 → A) (j : Fin 2) :
                        (kPt t w).2 j = w j

                        The item of the set s, padded with the minimum a₀.

                        Equations
                        Instances For

                          The bit position (e, x): the x-th position of the block of e.

                          Equations
                          Instances For

                            The lowest position of the block of e.

                            Equations
                            Instances For
                              @[simp]
                              theorem DescriptiveComplexity.KnapRed.kItem_fst {A : Type} (a₀ s : A) :
                              (kItem a₀ s).2 0 = s
                              @[simp]
                              theorem DescriptiveComplexity.KnapRed.kLow_fst {A : Type} (a₀ e : A) :
                              (kLow a₀ e).2 0 = e
                              @[simp]
                              theorem DescriptiveComplexity.KnapRed.kLow_snd {A : Type} (a₀ e : A) :
                              (kLow a₀ e).2 1 = a₀

                              Characterization of the interpreted relations #

                              @[simp]

                              The interpreted order is a linear order: the two tags in order, each carrying the lexicographic order on pairs.

                              The place values #

                              theorem DescriptiveComplexity.KnapRed.eq_kItem {A : Type} [FirstOrder.Language.setSystem.Structure A] [LinearOrder A] {a₀ : A} (ha₀ : IsBot a₀) {i : kInterp.Map A} (h : BWItem i) :
                              i = kItem a₀ (i.2 0) ∧ SSFam (i.2 0)

                              An item is the padded item of the set it carries.

                              theorem DescriptiveComplexity.KnapRed.bitRank_kLow {A : Type} [FirstOrder.Language.setSystem.Structure A] [LinearOrder A] {a₀ : A} (ha₀ : IsBot a₀) (e : A) :
                              bitRank BWLe BWPosn (kLow a₀ e) = Nat.card A * bitRank (fun (x1 x2 : A) => x1 ≤ x2) SSElem e

                              The block structure: the rank of the lowest position of the block of e is |A| times the rank of e, so its place value is (2 ^ |A|) ^ rank e – one digit of base 2 ^ |A| per ground element.

                              Weights and target, as base-2 ^ |A| numbers #

                              noncomputable def DescriptiveComplexity.KnapRed.base (A : Type) [Finite A] :

                              The base: one digit per ground element, |A| bits wide, which is above the number of sets, so digits never carry into the next block.

                              Equations
                              Instances For

                                The counting step #

                                Correctness #

                                Stated for an explicit cover and an explicit set of items, so that the same lemmas give the equivalence of the two decision problems and the bijection between their solutions (DescriptiveComplexity.Problems.Knapsack.CountingHardness).

                                def DescriptiveComplexity.KnapRed.itemsOf {A : Type} (a₀ : A) (G : A → Prop) (i : kInterp.Map A) :

                                The items of a subfamily: the padded items of its sets.

                                Equations
                                Instances For
                                  def DescriptiveComplexity.KnapRed.coverOfItems {A : Type} (a₀ : A) (S : kInterp.Map A → Prop) (s : A) :

                                  The subfamily of a set of items: the sets whose padded item is chosen.

                                  Equations
                                  Instances For
                                    theorem DescriptiveComplexity.KnapRed.subsetSum_itemsOf {A : Type} [FirstOrder.Language.setSystem.Structure A] [LinearOrder A] [Finite A] [Nonempty A] {a₀ : A} (ha₀ : IsBot a₀) {G : A → Prop} (hG : ExactCoverBy SSElem SSFam SSMem G) :
                                    (∀ (i : kInterp.Map A), itemsOf a₀ G i → BWItem i) ∧ ∑ᶠ (i : kInterp.Map A) (_ : i ∈ {i : kInterp.Map A | itemsOf a₀ G i}), BWWeight i = BWTarget (kInterp.Map A)

                                    The items of an exact cover sum to the target.

                                    theorem DescriptiveComplexity.KnapRed.exactCoverBy_coverOfItems {A : Type} [FirstOrder.Language.setSystem.Structure A] [LinearOrder A] [Finite A] [Nonempty A] {a₀ : A} (ha₀ : IsBot a₀) {S : kInterp.Map A → Prop} (hSi : ∀ (i : kInterp.Map A), S i → BWItem i) (hsum : ∑ᶠ (i : kInterp.Map A) (_ : i ∈ {i : kInterp.Map A | S i}), BWWeight i = BWTarget (kInterp.Map A)) :

                                    A set of items summing to the target is an exact cover.

                                    Correctness of the reduction: the set system has an exact cover iff the interpreted binary-weighted instance has a set of items summing to the target.

                                    Exact Cover FO-reduces to Knapsack, over any linear order on the input: one item per set, one digit block of |A| bits per ground element, weights carrying a 1 in the block of each of their elements and the target a 1 in every block.

                                    Equations
                                    • One or more equations did not get rendered due to their size.
                                    Instances For