Communication
Free
Faster access than browser!

# BPP (complexity)

In computational complexity theory, BPP, which stands for bounded-error probabilistic polynomial time is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded away from 1/3 for all instances. [1]

52 relations: AKS primality test, Arthur–Merlin protocol, Avi Wigderson, Boolean circuit, BQP, Chernoff bound, Christos Papadimitriou, Complement (complexity), Computational complexity theory, Conjecture, Decision problem, E (complexity), Exponential decay, EXPTIME, Lance Fortnow, Las Vegas algorithm, László Babai, Leonard Adleman, Low (complexity), Manindra Agrawal, Mathematical constant, Michael Sipser, Monte Carlo algorithm, Neeraj Kayal, Nitin Saxena, Noam Nisan, NP (complexity), NP-completeness, Oracle machine, P/poly, PH (complexity), Polynomial hierarchy, PostBQP, Postselection, PP (complexity), Primality test, Prime number, Probabilistic Turing machine, Probability, Pseudorandom number generator, Quantum computing, Random oracle, Randomized algorithm, RP (complexity), Russell Impagliazzo, Schwartz–Zippel lemma, Simon Fraser University, Sipser–Lautemann theorem, Subset, Time complexity, ... Expand index (2 more) »

## AKS primality test

The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, computer scientists at the Indian Institute of Technology Kanpur, on August 6, 2002, in a paper titled "PRIMES is in P".

## Arthur–Merlin protocol

In computational complexity theory, an Arthur&ndash;Merlin protocol is an interactive proof system in which the verifier's coin tosses are constrained to be public (i.e. known to the prover too).

## Avi Wigderson

Avi Wigderson (אבי ויגדרזון; born 9 September 1956) is an Israeli mathematician and computer scientist.

## Boolean circuit

In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for digital logic circuits.

## BQP

In computational complexity theory, BQP (bounded error quantum polynomial time) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.

## Chernoff bound

In probability theory, the Chernoff bound, named after Herman Chernoff but due to Herman Rubin, gives exponentially decreasing bounds on tail distributions of sums of independent random variables.

Christos Harilaos Papadimitriou (Greek: Χρήστος Χαρίλαος Παπαδημητρίου; born August 16, 1949, Athens) is a Greek engineer, computer scientist, and professor of Computer Science at the University of California, Berkeley.

## Complement (complexity)

In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers.

## Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.

## Conjecture

In mathematics, a conjecture is a conclusion or proposition based on incomplete information, but for which no proof has been found.

## Decision problem

In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters.

## E (complexity)

In computational complexity theory, the complexity class E is the set of decision problems that can be solved by a deterministic Turing machine in time 2O(n) and is therefore equal to the complexity class DTIME(2O(n)).

## Exponential decay

A quantity is subject to exponential decay if it decreases at a rate proportional to its current value.

## EXPTIME

In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) 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 terms of DTIME, We know and also, by the time hierarchy theorem and the space hierarchy theorem, that so at least one of the first three inclusions and at least one of the last three inclusions must be proper, but it is not known which ones are.

## Lance Fortnow

Lance Jeremy Fortnow (born August 15, 1963) is a computer scientist known for major results in computational complexity and interactive proof systems.

## Las Vegas algorithm

In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure.

## László Babai

László (Laci) Babai (born July 20, 1950 in Budapest) from Babai's web site, retrieved 2010-07-30.

Leonard Max Adleman (born December 31, 1945) is an American theoretical computer scientist and professor of computer science and molecular biology at the University of Southern California.

## Low (complexity)

In computational complexity theory, a complexity class B is said to be low for a complexity class A if AB.

## Manindra Agrawal

Manindra Agrawal (born 20 May 1966) is a professor at the Department of Computer Science and Engineering and the Dean of Faculty Affairs (DoFA) at the Indian Institute of Technology, Kanpur.

## Mathematical constant

A mathematical constant is a special number, usually a real number, that is "significantly interesting in some way".

## Michael Sipser

Michael Fredric Sipser (born September 17, 1954) is a theoretical computer scientist who has made early contributions to computational complexity theory.

## Monte Carlo algorithm

In computing, a Monte Carlo algorithm is a randomized algorithm whose running time is deterministic, but whose output may be incorrect with a certain (typically small) probability.

## Neeraj Kayal

Neeraj Kayal (नीरज कयाल) is an Indian computer scientist.

## Nitin Saxena

Nitin Saxena (नितिन सक्सेना) (born 3 May 1981) is an Indian scientist, active in the fields of mathematics and theoretical computer science.

## Noam Nisan

Noam Nisan (born 1961) is an Israeli computer scientist, a professor of computer science at the Hebrew University of Jerusalem.

## NP (complexity)

In computational complexity theory, NP is one of the most fundamental complexity classes.

## NP-completeness

In computational complexity theory, a decision problem is NP-complete when it is both in NP and NP-hard.

## Oracle machine

In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems.

## P/poly

In computational complexity theory, P/poly is the complexity class of languages recognized by a polynomial-time Turing machine with a polynomial-bounded advice function.

## PH (complexity)

In computational complexity theory, the complexity class PH is the union of all complexity classes in the polynomial hierarchy: PH was first defined by Larry Stockmeyer.

## Polynomial hierarchy

In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines.

## PostBQP

In computational complexity theory, PostBQP is a complexity class consisting of all of the computational problems solvable in polynomial time on a quantum Turing machine with postselection and bounded error (in the sense that the algorithm is correct at least 2/3 of the time on all inputs).

## Postselection

In probability theory, to postselect is to condition a probability space upon the occurrence of a given event.

## PP (complexity)

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.

## Primality test

A primality test is an algorithm for determining whether an input number is prime.

## Prime number

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

## Probabilistic Turing machine

In computability theory, a probabilistic Turing machine is a non-deterministic Turing machine which randomly chooses between the available transitions at each point according to some probability distribution.

## Probability

Probability is the measure of the likeliness that an event will occur.

## Pseudorandom number generator

A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers.

## Quantum computing

Quantum computing studies theoretical computation systems (quantum computers) that make direct use of quantum-mechanical phenomena, such as superposition and entanglement, to perform operations on data.

## Random oracle

In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every unique query with a (truly) random response chosen uniformly from its output domain.

## Randomized algorithm

A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic.

## RP (complexity)

In computational complexity theory, randomized polynomial time (RP) is the complexity class of problems for which a probabilistic Turing machine exists with these properties.

## Russell Impagliazzo

Russell Impagliazzo is a professor of computer science at the University of California, San Diego.

## Schwartz–Zippel lemma

In mathematics, the Schwartz–Zippel lemma is a tool commonly used in probabilistic polynomial identity testing, i.e. in the problem of determining whether a given multivariate polynomial is the 0-polynomial (or identically equal to 0).

## Simon Fraser University

Simon Fraser University (SFU) is a public research university in Burnaby, British Columbia, Canada, with its main campus on Burnaby Mountain and satellite campuses in Downtown Vancouver and Surrey.

## Sipser–Lautemann theorem

In computational complexity theory, the Sipser–Lautemann theorem or Sipser–Gács–Lautemann theorem states that Bounded-error Probabilistic Polynomial (BPP) time, is contained in the polynomial time hierarchy, and more specifically Σ2 ∩ Π2.

## Subset

In mathematics, especially in set theory, a set A is a subset of a set B, or equivalently B is a superset of A, if A is "contained" inside B, that is, all elements of A are also elements of B. A and B may coincide.

## Time complexity

In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input.

## Turing machine

A Turing machine is an abstract "machine" that manipulates symbols on a strip of tape according to a table of rules; to be more exact, it is a mathematical model that defines such a device.

## ZPP (complexity)

In complexity theory, ZPP (zero-error probabilistic polynomial time) is the complexity class of problems for which a probabilistic Turing machine exists with these properties.

## References

Hey! We are on Facebook now! »