This article is about the complexity class. For the Black nationalist organization, see Black Panther Party. Black nationalist flag Black nationalism is a political and social movement prominent in the 1960s and early 70s among African Americans in the United States. ... Logo of the Black Panther Party The Black Panther Party (originally called the Black Panther Party for Self-Defense) is a revolutionary Black nationalist organization in the United States that formed in the late 1960s and grew to national prominence before falling apart due to a combination of internal problems...

In complexity theory, BPP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of at most 1/3 for all instances. The abbreviation BPP refers to Bounded-error, Probabilistic, Polynomial time. Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ... In logic, a decision problem is determining whether or not there exists a decision procedure or algorithm for a class S of questions requiring a Boolean value (i. ... In computability theory, a probabilistic Turing machine is a non-deterministic Turing machine which randomly chooses between the available transitions at each point with equal probability. ... In computational complexity theory, Polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ... The word probability derives from the Latin probare (to prove, or to test). ...

If a problem is in BPP, then there is an algorithm for it that is allowed to flip coins and make random decisions. It is guaranteed to run in polynomial time. On any given run of the algorithm, it has a probability of at most 1/3 of giving the wrong answer. That is true, whether the answer is YES or NO.

The choice of 1/3 in the definition is arbitrary. It can be any constant between 0 and 1/2 (exclusive) and the set BPP will be unchanged; however, this constant must be independent of the input. The idea is that there is a probability of error, but if the algorithm is run many times, the chance that the majority of the runs are wrong drops off exponentially as a consequence of the Chernoff bound [1]. This makes it possible to create a highly accurate algorithm by merely running the algorithm several times and taking a "majority vote" of the answers. A mathematical constant is a quantity, usually a real number or a complex number, that arises naturally in mathematics and does not change. ... A quantity is said to be subject to exponential decay if it decreases at a rate proportional to its value. ... In probability theory, the Chernoff bound, named after Herman Chernoff, gives a lower bound for the success of majority agreement for n independent, equally likely events. ...

BPP is one of the largest practical classes of problems, meaning most problems of interest in BPP have efficient probabilistic algorithms that can be run quickly on real modern machines, by the method described above. For this reason it is of great practical interest which problems and classes of problems are inside BPP. A randomized algorithm is an algorithm which is allowed to flip a truly random coin. ...

It is known that BPP is closed under complement; that is, BPP=Co-BPP. It is an open question whether BPP is a subset of NP. It is also an open question whether NP is a subset of BPP; if it is, then NP=RP (many consider this unlikely, since it would imply practical solutions for a range of difficult NP-complete problems). It is known that RP is a subset of BPP, and BPP is a subset of PP. It is not known whether those two are strict subsets. BPP is contained in PH. A is a subset of B If X and Y are sets and every element of X is also an element of Y, then we say or write: X is a subset of (or is included in) Y; X ⊆ Y; Y is a superset of (or includes) X; Y ⊇ X... In computational complexity theory, NP (Non-deterministic Polynomial time) is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use... RP or rp may stand for: Received Pronunciation Republic of Poland Republic of the Philippines RP, a complexity class in computational complexity theory Rupiah Recommended practice Re-Purchase Agreement Role-playing Retinitis pigmentosa Rapid prototyping Rocket Power Rocket projectile Rating Pending, a rating by ESRB, that does not yet have... In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. ... In computational complexity theory, the complexity class PH is the union of all complexity classes in the polynomial hierarchy: PH is contained in the complexity classes PPP (the class of problems that are decidable by a polynomial time Turing machine with an access to PP oracle) and PSPACE. PH has...

The existence of certain strong pseudorandom number generators is conjectured by most experts of the field. This conjecture implies that randomness does not give additional computational power to polynomial time computation, that is, P=RP=BPP. We also have P = BPP if EXPTIME collapses to MA, ¹ if the exponential-time hierarchy collapses to E = DTIME(2^O(n)), ¹ or if E has exponential circuit complexity.² A pseudorandom number generator (PRNG) is an algorithm that generates a sequence of numbers, the elements of which are approximately independent of each other. ... Mathmatical and Non-Mathamatical Definitions In mathematics, a conjecture is a mathematical statement which has been proposed as a true statement, but which no one has yet been able to prove or disprove. ... In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. ... In computational complexity theory, an Arthur-Merlin protocol is an interactive proof system in which the verifiers coin tosses are constrained to be public (i. ...

For a long time, one of the most famous problems that was known to be in BPP but not known to be in P was the problem of determining whether a given number is a prime. However, in the 2002 paper PRIMES in P, Manindra Agrawal and his students Neeraj Kayal and Nitin Saxena found a deterministic polynomial-time algorithm for this problem, thus showing that it is in P. In mathematics, a prime number (or prime) is a natural number greater than one whose only positive divisors are one and itself. ...

BPP is low for itself, meaning that a BPP machine with the power to solve BPP problems instantly is not any more powerful. In computational complexity theory, it is said that a complexity class B is low for a complexity class A if AB = A; that is, A with an oracle for B is equal to A. Such a statement implies that an abstract machine which solves problems in A achieves no additional...

This class is defined for an ordinary Turing machine plus a source of randomness. The corresponding class for a quantum computer is BQP. Artists conception of a universal Turing machine. ... Molecule of alanine used in NMR implementation of error correction. ... BQP, in computational complexity theory, stands for Bounded error, Quantum, Polynomial time. It denotes the class of problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/4 for all instances. ...

External links

• Princeton CS 597E: Derandomization paper list
• Harvard CS 225: Pseudorandomness

References

• László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity, 3:307–318. 1993.
• Russell Impagliazzo and Avi Wigderson. P=BPP if E requires exponential circuits: Derandomizing the XOR Lemma.
• Valentine Kabanets. "CMPT 710 - Complexity Theory: Lecture 16". Simon Fraser University. 2003.

In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. ... Simon Fraser University (SFU) is located in Burnaby, British Columbia, Canada, a suburb of Vancouver, British Columbia. ...

Footnotes

1. Nisan and Wigderson.

2. Impagliazzo and Wigderson.