Probabilistic Complexity Theory - Where Randomness Helps

Where Randomness Helps

When the model of computation is restricted to Turing machines, it is currently an open question whether the ability to make random choices allows some problems to be solved in polynomial time that cannot be solved in polynomial time without this ability; this is the question of whether P = BPP. However, in other contexts, there are specific examples of problems where randomization yields strict improvements.

• Based on the initial motivating example: given an exponentially long string of 2k characters, half a's and half b's, a random access machine requires at least 2k−1 lookups in the worst-case to find the index of an a; if it is permitted to make random choices, it can solve this problem in an expected polynomial number of lookups.
• In communication complexity, the equality of two strings can be verified using bits of communication with a randomized protocol. Any deterministic protocol requires bits.
• The volume of a convex body can be estimated by a randomized algorithm to arbitrary precision in polynomial time. Bárány and Füredi showed that no deterministic algorithm can do the same. This is true unconditionally, i.e. without relying on any complexity-theoretic assumptions.
• A more complexity-theoretic example of a place where randomness appears to help is the class IP. IP consists of all languages that can be accepted (with high probability) by a polynomially long interaction between an all-powerful prover and a verifier that implements a BPP algorithm. IP = PSPACE. However, if it is required that the verifier be deterministic, then IP = NP.
• In a chemical reaction network (a finite set of reactions like A+B → 2C + D operating on a finite number of molecules), the ability to ever reach a given target state from an initial state is decidable, while even approximating the probability of ever reaching a given target state (using the standard concentration-based probability for which reaction will occur next) is undecidable. More specifically, a Turing machine can be simulated with arbitrarily high probability of running correctly for all time, only if a random chemical reaction network is used. With a simple nondeterministic chemical reaction network (any possible reaction can happen next), the computational power is limited to primitive recursive functions.
• The inherent randomness of algorithms such as Hyper-encryption, Bayesian networks, Random neural networks and Probabilistic Cellular Automata was harnessed by Krishna Palem et al. to design highly efficient hardware systems using Probabilistic CMOS or PCMOS technology that were shown to achieve gains that are as high as a multiplicative factor of 560 when compared to a competing energy-efficient CMOS based realizations.