Knapsack is in NP #
The Σ₁ definition of DescriptiveComplexity.Knapsack. Verifying that a set of
binary weights sums to the target is the one place in the catalog where the
certificate has to carry arithmetic: the guess is
sel, the chosen items;psum i p, the bits of the running total over the chosen items up toi;carry i p, the carries of the addition that appendsito that total,
and the kernel checks, first-order, that each step is a ripple-carry addition
– every bit the exclusive or of the three inputs, every carry their majority –
with no carry into the lowest position and none out of the highest. That the
chain really computes the sum is DescriptiveComplexity.binNum_ripple, and that a
chain exists whenever the sum fits is DescriptiveComplexity.exists_ripple
(DescriptiveComplexity.Numbers.BinRel).
Walking the items in order is what makes a single relation psum enough, and
it is why the vocabulary orders the items and not only the bit positions.
The tgt symbol over the sum.
Instances For
The single existential block of the Σ₁ definition of Knapsack: the
chosen items (unary), the running partial sums and the carries (binary, an
item and a bit position).
Equations
- One or more equations did not get rendered due to their size.
Instances For
The relation variables of the block.
- sel : KnapsackGuessBlockIx
The chosen items.
- pS : KnapsackGuessBlockIx
The running partial sums:
pS i pis the bitpof the total up to the itemi. - carry : KnapsackGuessBlockIx
The carries of the step appending an item.
Instances For
The bit symbol over the sum.
Instances For
The posn symbol over the sum.
Instances For
The item symbol over the sum.
Instances For
The le symbol over the sum.
Instances For
Equations
- One or more equations did not get rendered due to their size.
The vocabulary of the kernel: the instance expanded by the block.
Equations
Instances For
Formula builders #
x is an item, as a formula.
Equations
Instances For
x is a bit position, as a formula.
Equations
Instances For
The weight of i has bit 1 at p, as a formula.
Equations
Instances For
The target has bit 1 at p, as a formula.
Equations
Instances For
x ≤ y, as a formula.
Equations
Instances For
x is chosen, as a formula.
Equations
Instances For
Bit p of the running total at i, as a formula.
Equations
Instances For
The carry at p of the step appending i, as a formula.
Equations
Instances For
x = y, as a formula.
Equations
Instances For
The bit that the item i contributes at p: its weight's bit, if it is
chosen.
Equations
Instances For
The majority of three formulas.
Equations
- DescriptiveComplexity.kMaj3F x y z = x ⊓ y ⊔ (x ⊓ z ⊔ y ⊓ z)
Instances For
i is the first item, as a formula.
Equations
- One or more equations did not get rendered due to their size.
Instances For
i is the last item, as a formula.
Equations
- One or more equations did not get rendered due to their size.
Instances For
j is the item right after i, as a formula.
Equations
- One or more equations did not get rendered due to their size.
Instances For
p is the lowest position, as a formula.
Equations
- One or more equations did not get rendered due to their size.
Instances For
p is the highest position, as a formula.
Equations
- One or more equations did not get rendered due to their size.
Instances For
q is the position right above p, as a formula.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The clauses #
Kernel clause: the order is reflexive.
Equations
Instances For
Kernel clause: the order is transitive.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Kernel clause: the order is antisymmetric.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Kernel clause: the order is total.
Equations
Instances For
Kernel clause: only items are chosen.
Equations
Instances For
Kernel clause: at the first item the running total is that item's contribution.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Kernel clause: each step adds a bit.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Kernel clause: each step propagates its carry.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Kernel clause: nothing is carried into the lowest position.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Kernel clause: nothing is carried out of the highest position.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Kernel clause: at the last item the running total is the target.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Kernel clause: with no item at all, the target must be zero.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The first-order kernel of the Σ₁ definition of Knapsack.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Kernel clause of the counting kernel: the running totals are stored at items and positions only.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Kernel clause of the counting kernel: the carries are stored at positions and at the items that are not the first one only.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The counting kernel of Knapsack: the kernel of its Σ₁ definition, and
the two clauses that leave nothing of a certificate unconstrained, so that a
solution has exactly one.
Equations
Instances For
Realization #
What the counting kernel says of an assignment of the block: the instance is well formed, the chosen elements are items, the two binary relations are a walk ending on the target, and they hold nowhere else.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The counting kernel says exactly what it should.
Membership #
Knapsack is Σ₁-definable: guess the chosen items, the running totals
and the carries, and check first-order that each step is a ripple-carry
addition whose last total is the target. Since NP is defined as
Σ₁-definability, this is the membership half of the NP-completeness of
Knapsack.