Concept

Assignment

A way of giving each of several people exactly one of several tasks, with no task handed out twice. The count of them grows as a factorial, so which one is best is settled by structure — a matching condition, or the corners of a polytope — rather than by trying them all.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

(p ∨ q) ∧ ¬r, drawn on the cube of 8 assignments. The assignments as corners of a cube, joined when they differ in one variable, with the satisfying corners filled.

A formula is a corner of a cube

A formula about three letters is a set of eight rows. Written as a table that is a list; drawn on a cube it is a shape — and the shape is what almost every later question in this field turns out to be about.

logic · truth functions

A table of shares written as a lottery over 3 whole assignments. A doubly stochastic table of shares, and beneath it the permutation matrices and weights that add up to it exactly, each drawn as a grid with one marked cell per row.

A lottery over whole assignments

A table of shares in which every person's shares add to one task and every task is exactly covered is never anything more than a mixture of whole assignments — and finding the mixture is a matter of taking one complete assignment out at a time.

applied · assignment

Named alongside it

The objects these essays reach for when they reach for this one.

Connective Convexity Doubly stochastic Fairness Hypercube Linear program Matching Normal form Permutation Propositional formula Satisfiability Tautology

All concepts