CS Theorems

Symptom You need to prove a language is not regular. Everyone points you at the pumping lemma, and you spend an afternoon losing to it. The statement is a nest of quantifiers: for every regular language there exists a pumping length $p$ such that for every string $w$ with $|w| \ge p$ there exists a decomposition $w = xyz$ with $|xy| \le p$ and $|y| > 0$ such that for all $i \ge 0$, $xy^i z$ is in the language. To use it you negate all of that and play a game against an adversary who picks $p$ and the decomposition while you pick $w$ and $i$. ...

Symptom Your service goes down. CPU pinned at 100% on one core, no memory growth, no error logs, requests timing out. The cause is a validation regex — something reasonable-looking like ^(a+)+$, or in real life a URL or email validator with nested quantifiers — matched against a 30-character string that happens not to match. The engine is exploring an exponential number of ways to split the input among the nested groups, and it will get there eventually, some time after the heat death of everything. ...

Symptom You need to test whether two arithmetic circuits compute the same polynomial. The deterministic approach is to expand both into normal form, and the expansion is exponentially large. The randomized approach takes four lines. Pick a random point, evaluate both circuits there, compare. If they differ as polynomials, the Schwartz-Zippel lemma says a random point catches it with probability at least $1 - d/|S|$. Repeat a few times and the error is negligible. ...

Symptom You have a string algorithm. Edit distance between two sequences, the classic dynamic program, $O(n^2)$ time. It has been in production for years. Now the inputs are genome-scale. At $n = 10^5$ characters, $n^2 = 10^{10}$ operations, about 10 seconds at a billion ops per second. At $n = 10^6$ it is $10^{12}$ operations, about 1000 seconds — seventeen minutes for one pair of strings. You need to do a million pairs. ...

Symptom You have just read T030 and you are demoralized. Relativization kills the techniques that treat machines as black boxes. Natural proofs kill the combinatorial ones, assuming pseudorandom functions exist. Between them they appear to rule out everything anyone knows how to do, and the honest summary of fifty years is that nobody can prove any interesting problem is hard. ...

Symptom You have spent this whole part learning that information wants to be copied. Entropy bounds compression (T018), Huffman hits the bound (T020), redundancy buys error correction (T021). Every result so far treats “make another copy” as the free operation — the thing you do without thinking, the reason cp has no interesting failure modes. ...

Symptom Your dashboard shows CPU utilization averaging 40%, comfortably under budget. Users are reporting timeouts. You add more logging and the average stays at 40%. Eventually someone captures a one-second trace and finds the truth: the service spikes to 100% for eight seconds out of every ninety, and your monitoring samples every sixty seconds. The spikes are real, periodic, and invisible. ...

Symptom A node in your cluster is not down. It is worse than down. Its disk is returning corrupted blocks that pass the checksum because the checksum is corrupted too. Or a NIC with a firmware bug is duplicating and reordering frames. Or a bad memory module flipped a bit in a config value and the node now believes it owns a shard it does not. Or someone has root on one machine. ...

Symptom Your cluster of five nodes elects a leader. It works. It has worked for a year. Then one afternoon a garbage collection pause on the leader runs for twelve seconds. The followers time out, start an election, and elect a new leader. The old leader wakes up, has no idea it was deposed, and keeps serving writes. For a few hundred milliseconds you have two leaders, and if your fencing is not airtight, two writes that should have been ordered land in an order nobody chose. ...

Symptom You took the lesson from T058 and stopped trusting wall clocks. Every event now carries a Lamport timestamp, and your writes are ordered by it. The vanishing updates stopped. ...

Symptom Two writes to the same key. Which one wins? Your first instinct is timestamps: whichever has the later wall-clock time is newer. This works in testing. In production you get a bug report saying an update vanished, and when you dig in, node B’s clock was 40 ms behind node A’s, so B’s later write carried an earlier timestamp and lost. NTP is running. NTP does not make clocks identical, it makes them close, and “close” is not “ordered.” ...

Symptom Your problem is NP-hard, and yet it keeps being easy. You are computing a minimum vertex cover to select monitoring points in a network. Twelve thousand nodes. NP-hard, per T028, so you brace for the worst — and the answer comes back in under a second, every time. The cover is small, around thirty nodes, because the network is sparse and the interesting nodes are few. ...

Symptom You have accepted that the problem is NP-hard. Now what? The literature offers a wall of results with numbers attached: 2-approximation, $\ln n$-approximation, PTAS, FPTAS, 0.878. Nobody explains what these numbers buy you, how they are proved, or how they connect to the heuristic you already wrote. Meanwhile your greedy heuristic is running in production and you have no idea whether it is within 5% or a factor of 50 of optimal, because you cannot compute the optimum to compare against — that was the whole problem. ...

Symptom You gave up on exact (T028) and went looking for an approximation. Vertex cover: you find a 2-approximation in four lines. Knapsack: an FPTAS, any accuracy you want. Encouraged, you go looking for the same for max-clique, and you find nothing. Not “nothing good” — the best known ratio is around $n/(\log n)^2$, which on a 10,000-vertex graph means the algorithm might return a clique nearly 60 times smaller than the true maximum. That is not an approximation, it is a rumour. ...

Symptom Product wants the daily unique-visitor count. You have a firehose of events. The obvious implementation is a set. Add each visitor ID, report the size. At a billion distinct IDs, eight bytes each, that is 8 GB before any hash table overhead, and in practice a HashSet will cost you two to three times that. Per day. Per dimension you want to slice by. Multiply by country, by platform, by campaign, and the memory bill is absurd for a number nobody looks at past two significant figures. ...

Symptom Your service went down under a hash collision attack. Somebody noticed your web framework put POST parameters into a hash table, found thousands of distinct keys colliding under its hash function, and posted a form with 20,000 of them. Every insert walked a chain. Quadratic behaviour, one CPU pinned per request, service dead. This actually happened, across PHP, Python, Ruby, Java and .NET in 2011, and again against Rust’s default HashMap before it switched to SipHash. ...

Symptom You fit a model. It scores 94% on training data and 71% on held-out data. So you simplify: fewer parameters, more regularization. Training drops to 88%, held-out rises to 84%. You simplify further and both drop. Somewhere in there was an optimum, and you found it by trial and error, with a validation set and patience. ...

Symptom You have two files, each exactly one megabyte. The first is a megabyte of the byte 0x00. The second is a megabyte from /dev/urandom. Gzip the first and you get a few hundred bytes. Gzip the second and you get slightly more than a megabyte, because the header costs something and there is nothing to exploit. ...

Symptom You have read T026 and T027 and you are wondering the obvious thing. Fifty years. Thousands of researchers. A million-dollar prize. And P vs NP has not moved. That is strange — most famous problems yield partial results, near misses, special cases that suggest the shape of the answer. Here there is almost nothing. We cannot even prove that NP requires more than linear-size circuits, which is a laughably weak statement compared to what everyone believes. ...

Symptom Three weeks into a project, you are still trying to write an exact algorithm. The problem is yours and it looks specific: assign delivery vans to routes such that every stop is covered, no van exceeds its capacity, and the total distance is minimized. Nothing in the literature matches it exactly. So you keep going — better data structures, smarter pruning, a cleverer greedy pass with a repair step — and each version works on your test set and falls over on production data. ...