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 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 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. ...
Symptom You know reductions (T017): to prove your problem hard, reduce a known-hard problem to it. Fine. But that begs the obvious question, and it is the question a sharp colleague asks the first time you use the technique. ...
Symptom You are specifying ECC memory for a fleet. The vendor quotes SECDED: single error correct, double error detect, at 8 check bits per 64 data bits. That is 12.5% overhead, and someone in the room asks the obvious question — why not correct two errors? Or three? What does it cost? ...
Symptom You are compressing a log file. The symbols are wildly skewed: INFO is 90% of the lines, WARN is 9%, ERROR and FATAL split the rest. Fixed-width two-bit codes give you exactly 2 bits per symbol, and entropy (T018) says the floor is about 0.53 bits. There is a factor of four sitting there. ...
Symptom You have 100 backends and a load balancer hashing request IDs to pick one. Expected load per backend is exactly 1%, and you have checked the hash is good. ...
Symptom You have a new problem. Your build system needs to decide whether two configuration files can ever produce conflicting outputs. Or your linter needs to decide whether a regex with backreferences can match a string of a given length. Or your scheduler needs to decide whether a set of periodic tasks is feasible. ...
Symptom The proof assistant is failing you. You are trying to verify a piece of concurrent code in Coq or Lean, and the tool will not accept your termination argument. A colleague says, without much conviction, “well, Gödel — you can’t prove everything anyway.” ...
Symptom Write a program that prints its own source code. No file I/O, no reading __file__, no cheating. The first attempt fails instantly. To print the source you must contain the source, and then the containing text is also part of the source, so you must contain that too. The regress is obviously infinite, and most people conclude after ten minutes that the task is impossible. ...
Symptom Your service handles four billion requests a month and you want the error rate. Computing it exactly means a job over four billion log lines. Someone suggests sampling ten thousand of them. ...
Symptom You have a dynamic array. push writes one element and bumps a counter, which is clearly $O(1)$ — except when the array is full, in which case it allocates a new buffer of twice the size, copies every element across, and frees the old one. That is $O(n)$. ...
Symptom You need the largest and second-largest element of an array. The obvious way is two passes: $n-1$ comparisons for the max, then $n-2$ for the max of the rest. That is $2n - 3$. ...
Symptom Every general-purpose sort in every standard library is $O(n \log n)$. Timsort, introsort, pdqsort, merge sort, heapsort. Decades of work by extremely motivated people, an enormous amount of money riding on it, and they all land on the same exponent. ...
Symptom You gzip a log file and it drops to 8% of its original size. You gzip the already-gzipped file and it gets slightly bigger. Somebody asks why, and the honest answer you have is “because it’s already compressed,” which is a restatement, not a reason. ...
Symptom The security team asks for a scanner with no false positives and no false negatives. Every piece of malware caught, nothing legitimate quarantined. The platform team asks whether the analyzer can flag every function that performs I/O, so the pure ones can be cached automatically. ...