L3

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 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 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 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 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 Your link drops 1% of bits. You need reliable delivery, so you triple every bit and take a majority vote. Now an error needs two of three bits to flip, which happens with probability about $3 \times 10^{-4}$ — better, but you paid 3x in bandwidth and the error rate is still not zero. ...