archive · taxonomy
The complexity zoo
Every transmission and every instrument, filed by how hard it is to think through. Click a ring to filter.
- Ptractable
- Polynomial time. Deterministic, tractably solvable: notes, results, things that are simply done.
- NPverifiable
- Nondeterministic polynomial time. Hard to find, easy to check: problems, puzzles and conjectures with evidence.
- PSPACEstrategic
- Polynomial space. Reversible computing, games and their state spaces: essays that play many moves ahead.
- EXPexplosive
- Exponential time. The limits of simulation: long builds, deep searches, things that provably cannot be done fast.
- REundecidable
- Recursively enumerable. The halting problem, Rice’s theorem, Chaitin’s Ω: questions a machine can confirm but never refute.
- № 007GUZEN: the dice are a 48-bit numberPtractable
- № 006ANTEVAULT: add, then multiplyPSPACEstrategic
- № 005A memory leak has a shapePSPACEstrategic
- № 004You need coherenceNPverifiable
- № 003Rule 137: eight bits that compute everythingREundecidable
- № 002Gliders are messagesNPverifiable
- № 001Hello, colonyPtractable
- instrument0–255Atlas of the 256 elementary automataRunning an elementary automaton for n steps on n cells takes O(n²) time, and every property on its labels is checked by exhaustive or polynomial computation.Ptractable
- instrument¬Glider logic: a NOT gate made of collisionsEvaluating a Boolean circuit is P-complete. This is the gate such circuits are built from.Ptractable
- instrument♩ ×8Tamburo 8: an automaton drum machineAn eight-cell automaton has only 2⁸ states, so every evolving groove falls into a cycle that is found in polynomial time.Ptractable
- instrument♪ ×32Orfeo 32: an underworld synthesizerFux’s rules only compare neighbouring notes, so the best counterpoint is a shortest path: O(n·k³) by dynamic programming. Everything else is a finite-state machine.Ptractable
- instrument34Melencolia I: a vocoder for sad songsA channel vocoder costs a fixed amount of work per band per sample, and the saddest four-chord phrase is a longest path in a layered chord graph, found by dynamic programming.Ptractable
- instrumentE(3,8)Genoma: a tape sampler, an 8-bit looper and an FM grooveboxEvery gene, loop and voice costs a fixed amount of work per sample, and a Euclidean rhythm of k pulses in n steps is laid out in O(n) time, as evenly as a straight line drawn on a grid.Ptractable
- instrument⋰ ×64Stochos 64: a stochastic MIDI sequencerOne pattern holds 2^1024 gate configurations; searching them by brute force takes exponential time, which is why the generators exist.EXPexplosive
- instrument⏚⟳Palinsesto: an effect pedalIts spectral mask is Rule 110, which is Turing-complete: whether the mask ever settles into a repeating pattern is, in general, undecidable.REundecidable
- instrument⎍⇄⌁Officina: VCV Rack, Pure Data and Orca, wired as one studioPure Data and Orca are programming languages: whether a patch or a grid ever falls silent is the halting problem, undecidable in general.REundecidable
- instrument▮▯▮▮Trappola 808: a trap drum machine after the 808’s circuits and its producersA two-bar pattern is a finite table read in a loop: every step costs the same, and the whole thing runs in time linear in its length.Ptractable
- instrument▣▣▣▢Polvere 404: the SP-404SX sampler, its pads, effects and pattern sequencerEvery pad press plays a buffer and every pattern is a finite list of hits read in a loop: each step takes a bounded amount of work.Ptractable
- instrumentφ⟲AaAutografo: a text that copies itself, lives by Conway’s rules and singsIts grid can run the Game of Life, which is Turing-complete: whether the text ever dies out, or settles, is undecidable in general.REundecidable
- instrument⟁⟁⟁Felce: musical fractals, from prolation canons to L-systems and a model’s textEach level of a fractal melody is the level above with every note replaced: a fixed amount of work for each note, so linear in the length of what is played.Ptractable
- instrument◐⇶✦Lanterna: a TouchDesigner for the browser, where cellular automata play musicA feedback loop of image operators can run the Game of Life, which is Turing-complete: whether a network ever settles is undecidable.REundecidable
- instrument⌂ 48Castello: the Bastl Kastle 2, its firmware in the browserEvery block of 48 samples is a fixed amount of work that must be done before the next one is due: a real-time machine is a polynomial-time machine with a deadline.Ptractable
- instrument⌁⌁⌁Cervello: an IDM workstationWith mutation on, whether the machine ever plays a given bar again is a reachability question over its state space: the kind that lives in polynomial space.PSPACEstrategic
- instrumentI–V–?Attrattore: a chaotic chord progression machineWhether any progression satisfies a set of harmonic constraints is a constraint-satisfaction problem, NP-complete in general: easy to check, hard to find.NPverifiable
- instrument◇—◇Network of transmissions and ideasForce-directed layout converges in polynomial time per iteration; the graph itself is small and explicit.Ptractable
- instrumentB3/S23Lab: Life-like, Lenia and SmoothLifeOn a bounded board, Life can simulate any polynomial-space Turing machine, so predicting its future is PSPACE-hard.PSPACEstrategic
- instrumentC×MANTEVAULT: a poker rogueliteA run is a few hundred moves long, so its best strategy is found by walking the game tree depth first: exponential time, polynomial space. Against a shuffled deck, that is a game against nature.PSPACEstrategic
- instrument2^48GUZEN: a synthesizer ruled by chanceAll of its chance is one 48-bit random number generator, so a piece is a fixed function of its seed: constant work per sample, and the score can be found without rendering any audio.Ptractable
- instrumentB(122)Organismo 23: a drum machine you patch with clipsThere are 122 pins, and a patch is a way of putting them into groups. That is the Bell number B(122), about 6 × 10^148 patches, and some of them are feedback loops that can only be heard by running them.EXPexplosive
- instrumentK(s)Complexity unveiled: seed, thread, fold, measureKolmogorov complexity is uncomputable. Only its upper bounds can be enumerated, which is exactly an RE property.REundecidable