Matpic
mathematics, in pictures
Concept

Complexity

How the cost of a computation grows with the size of its input, ignoring constant factors. It is what separates a method that is usable at a million items from one that is usable at a thousand, and the separations are usually about which structure the method exploits.

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

16 ways to sort it. A small order with its 16 linear extensions counted, and for each incomparable pair the fraction of extensions putting one before the other.

How many ways to sort it

An order says some things come before others and leaves the rest open. Counting the orderings consistent with it measures how much is still unknown — and the counting is as hard as any counting problem gets.

discrete · Posets The shortest tree was already in the triangulation. The Delaunay triangulation of 20 sites in faint lines with the minimum spanning tree drawn over it in heavy ones. Every tree edge is a triangulation edge, and the circles on the longest few tree edges as diameters contain no other site.

The tree inside the triangulation

The shortest network joining a set of points is built from edges chosen by length, and the triangulation is built from edges chosen by an emptiness condition about circles. The two constructions share no step, and every edge of the first is an edge of the second.

geometry · Voronoi A scatter with no lines in it. 900 consecutive pairs from a generator that squares modulo a product of two primes. The points show no family of parallel lines, and an exhaustive search for a short relation between consecutive outputs finds none.

Randomness that has to be earned

A generator that resists prediction cannot be built out of a rule anybody can fit. It has to be built out of a computation believed hard to undo, and the belief is the load-bearing part — which makes cryptographic randomness a conditional statement rather than a construction.

computation · Pseudorandomness The corner that is a half on every edge. A 3-vertex graph beside a table of the 5 corners of its matching relaxation. 4 are whole and one assigns a half to every edge.

Where the corners stop being whole

Everything on this ladder rests on one property — the relaxation of the assignment problem has whole-numbered corners. Add a single edge that closes an odd cycle and the property fails, a corner appears with a half in every coordinate, and the problem changes character completely.

applied · Assignment One minimum, or several. Two curves side by side with their local minima marked: a convex one with a single minimum, and a fourth-power well with 2.

Where the guarantee stops

Convexity converts every downhill method into a correct one, and its absence removes the guarantee entirely rather than degrading it. What is left is a collection of partial answers, and knowing which of them apply to a given problem is most of what non-convex optimisation is.

analysis · Convexity

Named alongside it

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

RelaxationAssignmentBipartiteCircumcircleConjectureConvexityCounterexampleCounting argumentCryptographyDelaunay triangulationFactoringGradient

All concepts