Derandomization

Consider two calculation rules: “square the input” and “return the input”. They agree at 0 and 1 but differ at 2. A test choosing a number uniformly from 0 to 7 can miss the difference; three independent tests all miss with probability only 1 in 64. This illustrates how chance can help check an answer. Can every fast yes/no procedure with a guaranteed small chance of error be replaced by an always-correct fixed procedure that stays fast as inputs grow?[1] [2]

A randomized decision algorithm takes an input and a string of random bits, then answers yes or no. BPP requires polynomial running time and correctness with probability at least $2/3$ for each input, with probability taken over the bits, not over a distribution of inputs. P requires polynomial time and an always-correct deterministic answer. One route to $P=BPP$ constructs a generator whose output preserves the algorithm’s acceptance probability closely enough. If the generator is polynomial-time computable and uses $d=O(\log n)$ seed bits for inputs of length $n$, all $2^d$ seeds can be tried in polynomial time. An acceptance-probability change strictly below $1/6$ preserves the majority distinction between the two answers.[1] [2]

The small example has easy fixed tests; it does not settle the general question. Known broad routes assume that certain functions are hard for small logical circuits. Conditional results and successes for restricted procedures do not establish an unconditional replacement for every efficient randomized decision procedure.[1] [2]

The general construction remains conditional. For example, Impagliazzo and Wigderson show that an exponential-time-computable Boolean function requiring exponentially large circuits would imply $P=BPP$; the needed circuit lower bound is an assumption. The May 2026 work additionally exploits structure in random-choice strings: changing one randomly chosen bit of a successful string usually preserves success. Its generator results require stated hardness, error and structural conditions. These are not an unconditional equality for all BPP decision problems.[2] [3]

Random checks can test algebraic calculations without expanding every expression. Equally efficient fixed checks would turn such decisions into always-correct computations with polynomial running-time guarantees. The problem also connects reliable testing to the limits of circuits—networks of simple logical operations—rather than only to the supply of random bits.[1] [3]

Hardness can supply useful randomness: if a small circuit could distinguish a generator’s outputs well enough from true randomness, the construction would let it compute a function assumed hard. That contradiction justifies a small family of replacement tests. A lower bound excluding small circuits for one task can thus yield upper bounds—efficient deterministic algorithms—for a whole class of decisions. This connects algorithm design to the larger effort to understand which computations limited circuits cannot perform.[1] [3]