BPP (complexity)

In computational complexity theory, a branch of computer science, bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded by 1/3 for all instances. 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. BPP also contains P, the class of problems solvable in polynomial time with a deterministic machine, since a deterministic machine is a special case of a probabilistic machine. Informally, a problem is in BPP if there is an algorithm for it that has the following properties: It 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, whether the answer is YES or NO. A language L is in BPP if and only if there exists a probabilistic Turing machine M, such that M runs for polynomial time on all inputs For all x in L, M outputs 1 with probability greater than or equal to 2/3 For all x not in L, M outputs 1 with probability less than or equal to 1/3 Unlike the complexity class ZPP, the machine M is required to run for polynomial time on all inputs, regardless of the outcome of the random coin flips. Alternatively, BPP can be defined using only deterministic Turing machines. A language L is in BPP if and only if there exists a polynomial p and deterministic Turing machine M, such that M runs for polynomial time on all inputs For all x in L, the fraction of strings y of length p(|x|) which satisfy M(x,y) = 1 is greater than or equal to 2/3 For all x not in L, the fraction of strings y of length p(|x|) which satisfy M(x,y) = 1 is less than or equal to 1/3 In this definition, the string y corresponds to the output of the random coin flips that the probabilistic Turing machine would have made.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (20)

Related courses (6)

Related lectures (36)

Complexity class

In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of a type of computational problem, a model of computation, and a bounded resource like time or memory. In particular, most complexity classes consist of decision problems that are solvable with a Turing machine, and are differentiated by their time or space (memory) requirements.

BPP (complexity)

Randomized algorithm

A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output (or both) are random variables.

Correctness and Soundness of the Qubit Test

Explores the correctness and soundness of the Qubit Test, emphasizing probabilistic algorithms, trapdoors, and function inversion.

Belief Propagation on Trees PHYS-642: Statistical physics for optimization & learning

Explores Belief Propagation on trees, discussing cavity marginals, message passing algorithms, and the computation of free entropy.

Quantum Computation Delegation

Covers the concept of quantum computation delegation and the relationship between MIP and RE, addressing common FAQs and discussing helpful materials and interactions with quantum devices.

CS-459: Foundations of probabilistic proofs

Probabilistic proof systems (eg PCPs and IPs) have had a tremendous impact on theoretical computer science, as well as on real-world secure systems. They underlie delegation of computation protocols a

PHYS-641: Quantum Computing

After introducing the foundations of classical and quantum information theory, and quantum measurement, the course will address the theory and practice of digital quantum computing, covering fundament

MATH-489: Number theory in cryptography

The goal of the course is to introduce basic notions from public key cryptography (PKC) as well as basic number-theoretic methods and algorithms for cryptanalysis of protocols and schemes based on PKC