BPP

 Nota: Para o banco, veja Banco Privado Português.

Na teoria da complexidade computacional, BPP (inglês: Bounded-error Probabilistic Polinomial time, probabilístico de tempo polinomial comprometido à erros) é a classe de problemas de decisão solúveis por uma Máquina de Turing em tempo polinomial, com uma probabilidade de erro de no máximo 1/3 para todas as instâncias.

Algoritmo BPP (1 execução)
	Resposta produzida
Reposta correta	SIM	NÃO
SIM	≥ 2/3	≤ 1/3
NÃO	≤ 1/3	≥ 2/3
Algoritmo BPP (k execuções)
	Resposta produzida
Resposta correta	SIM	NÃO
SIM	> 1 − 2−ck	< 2−ck
NÃO	< 2−ck	> 1 − 2−ck
para alguma constante c > 0

Informalmente, um problema está em BPP se existe um algoritmo para ele que tenha as seguintes propriedades:

• É permitido "jogar moedas" e fazer decisões aleatórias
• É garantido que será executado em tempo polinomial
• Em qualquer dada execução do algoritmo, o mesmo tem a probabilidade de no máximo 1/3 de fornecer uma resposta errada, se a resposta for SIM ou NÃO.

Introdução

BPP é uma das classes de problemas mais práticas, o que significa que a maior parte dos problemas que dizem respeito à BPP possuem algoritmos probabilísticos eficientes que podem ser executados rapidamente em máquinas reais modernas. Por essa razão é de grande interesse prático saber que problemas e classes de problemas estão em BPP. BPP também contém P, a classe de problemas solúveis em tempo polinomial com uma máquina determinística, uma vez que a máquina determinística é um caso especial da máquina probabilística.

Na prática, uma probabilidade de erro de 1/3 pode não ser aceitável, contudo, a escolha de 1/3 para a definição é arbitrária. A probabilidade pode ser qualquer constante entre 0 e 1/2 (exclusivo) e o conjunto BPP será o mesmo. Nem mesmo preciso ser uma constante: a mesma classe de problemas é definida por permitir erros tão grandes quanto 1/2 − n^−c por um lado, ou exigir erros tão pequenos quanto 2^−nc por outro lado, onde c é qualquer constante positiva, e n é o tamanho da entrada. A ideia é que existe uma probabilidade de erro, mas o algoritmo é executado várias vezes, a chance que a maioria das execuções deem errado decai exponencialmente como consequência do Limite de Chernoff.^[1] Isso torna possível a criação de algoritmos de alta precisão através de meras execuções do algoritmo por várias vezes levando-se em conta uma "votação pela maioria" das respostas. Por exemplo, se alguém definiu a classe com a restrição de que o algoritmo pode estar errado com a probabilidade de no máximo 1/2¹⁰⁰, isso resultaria em uma mesma classe de problemas.

Definição

Uma linguagem L está na BPP se e somente se existe uma máquina de Turing probabilística, tal que:

• M é executada em tempo polinomial em toda entrada
• Para todo x em L, M dá 1 como saída com probabilidade maior que ou igual a 2/3
• Para todo x que não está em L, M 1 como saída com probabilidade menor que ou igual a 1/3

Ao contrário da classe de complexidade ZPP, é exigido que a máquina M execute em tempo polinomial para toda entrada, independentemente do resultado dos aleatórios lançamentos de moedas.

Alternativamente, BPP pode ser definido usando-se somente máquinas de Turing determinísticas. Uma linguagem L está na BPP se e somente se existe uma máquina de Turing determinística M e um polinômio p, tal que:

• M é executada em tempo polinomial em toda entrada
• Para todo x em L, a fração de cadeias y com tamanho p(|x|) que satisfaz M(x,y) = 1 é maior que ou igual a 2/3
• Para todo x que não está em L, a fração de cadeias y de tamanho p(|x|) que satisfaz M(x,y) = 1 é menor que ou igual a 1/3

Nessa definição, a cadeia y corresponde a saída dos lançamentos de moedas aleatórios que a máquina de Turing probabilística teria feito. Para algumas aplicações essa definição é preferível uma vez que ela não menciona máquinas de Turing probabilísticas.

Problemas

Problema de ciência da computação em aberto:

P = BPP ?

(mais problemas em aberto da ciência da computação)

Além dos problemas em P, que estão obviamente em BPP, sabia-se que muitos outros problemas estavam em BPP mas não era sabido se estavam em P. O número de problemas desse tipo é decrescente, e conjuctura-se que P = BPP.

Por um longo tempo, um dos problemas mais famosos que era sabido estar em BPP mas não se sabia se estava em P foi o problema de determinar se um dado número é primo. Contudo, na documentação de 2002 PRIMO está em P, Manindra Agrawal e seus estudantes Neeraj Kayal e Nitin Saxena encontraram um algoritmo determinístico de tempo polinomial para esse problema, assim mostrando que esse problema está em P.

Um importante exemplo de um problema em BPP (na verdade em co-RP) que ainda não se sabe se está em P é o teste polinomial de identidade, é o problema de determinar se um polinômio é igual a o polinômio zero. Em outras palavras, existe uma valoração de variáveis tal que quando o polinômio é avaliado o resultado é não-zero? É suficiente escolher cada valor das variáveis de forma uniforme e aleatória a partir de um subconjunto finito de pelo menos d valores para atingir a probabilidade de comprometimento de erro, onde d é o grau total do polinômio.^[2]

Classes relacionadas

Se o acesso à aleatoriedade é removido da definição de BPP, nós obtemos a complexidade da classe P. Na definição da classe, se nós substituirmos a máquina de Turing usual por um computador quântico, nós obtemos a classe BQP.

Um algoritmo Monte Carlo é um algoritmo aleatório que provavelmente está correto. Problemas na classe BPP possuem algoritmo Monte Carlo com tempo de execução comprometidamente polinomial. Isso é comparável ao algoritmo Las Vegas que é um algoritmo aleatório que ou dá como saída a resposta correta, ou gera como saída "falha" com uma baixa probabilidade. Algoritmos de Las Vegas com tempo de execução comprometidamente polinomial são usadas para definir a classe ZPP. Alternativamente, ZPP contém algoritmos probabilísticos que estão sempre corretos e possuem o esperado tempo de execução polinomial. Isso é mais fraco do que dizer que ele é um algoritmo de tempo polinomial, uma vez que ele pode executar em um tempo polinomal muito grande, mas com uma probabilidade muito baixa.

Propriedades teóricas de complexidade

É sabido que BPP é fechado sob o complemento; ou seja, BPP = co-BPP. BPP é baixa por si mesma, significando que a máquina BPP com o poder de resolver problemas BPP instantaneamente (uma BPP máquina oráculo) não é mais poderosa que a máquina sem essa poder extra. Em símbolos, BPP^BPP = BPP.

O relacionamento entre BPP e NP é desconhecido: não se sabe se BPP é um subconjunto de NP, NP é um subconjunto de BPP ou se eles são incomparáveis. Se NP está contido em BPP, o que é considerado improvável uma vez que isso implicaria soluções prática para problemas NP-completo, então NP = RP e PH ⊆ BPP.^[3]

Sabe-se que RP é um subconjunto de BPP, e BPP é um subconjunto de PP. Não se sabe se esses dois são subconjuntos estritos, visto que nós nem mesmo sabemos se P é subconjunto estrito de PSPACE. BPP está contido no segundo nível da hierarquia polinomial e portanto está contido em PH. Mais precisamente, o teorema de Sipser-Lautemann diz que BPP ⊆ Σ₂ ∩ Π₂. Como resultado, P = NP nos leva à P = BPP visto que PH entra em colapso para P nesse caso. Assim ou P = BPP ou P ≠ NP ou ambos.

O teorema de Adleman afirma que a pertinência de qualquer linguagem em BPP pode ser determinado pela família de circuitos booleanos de tamanho polinomial, o que significa que BPP está contido em P/poly.^[4] De fato, como uma consequência da prova desse fato, todo algoritmo BPP operando sob entradas de que dizem respeito ao tamanho pode ser "des-aleatoriezado" em um algoritmo determinístico usando uma cadeia fixa de bits aleatórios. Todavia, encontrar essa cadeia pode ser ser custoso.

Com relação aos oráculos, nós sabemos que existem oráculos A e B, tal que P^A = BPP^A e P^B ≠ BPP^B. Além disso, com relação ao oráculo aleatório com probabilidade 1, P = BPP e BPP é estritamente contido em NP e co-NP.^[5]

Desaleatorização

A existência de certos fortes geradores de números pseudoaleatórios é conjecturado por muitos especialístas da área. Essa conjectura implica que aleatoriedade não dá poder computacional adicional para computação em tempo polinomial, isto é, P = RP = BPP. Note que geradores comuns não são suficientes para mostra esse resultado; qualquer algoritmo probabilístico implementado usando um típico gerador de números irá sempre produzir resultados incorretos em certas entradas independente da semente (embora essas entradas possam ser raras).

László Babai, Lance Fortnow, Noam Nisan e Avi Wigderson mostraram que a menos que EXPTIME entre em colapso para MA, BPP está contido em i.o.-SUBEXP = ${\displaystyle \bigcap _{\varepsilon >0}{\hbox{i.o.-DTIME}}(2^{n^{\varepsilon }})}$.^[6] A classe i.o.-SUBEXP (inglês: infinitely often SUBEXP, frequentemente infinitamente SUBEXP, contêm problemas que possuem algoritmos de tempo sub-exponencial para infinitos tamanhos de entrada. Eles também mostraram que P = BPP se a hierarquia de tempo exponencial, que é definida em temos da hierarquia polinomial e E como E^PH, entrar em colapso para E; contudo, note que é usualmente suposto que a hierarquia de tempo exponencial não entra em colapso.

Russell Impagliazzo e Avi Wigderson mostraram que se qualquer problema em E, onde ${\displaystyle {\textrm {E}}={\textrm {DTIME}}\left(2^{O(n)}\right)}$, possui complexidade de circuito ${\displaystyle 2^{\Omega (n)}}$ então P = BPP.^[7]

Referências

1. http://www.cs.sfu.ca/~kabanets/cmpt710/lec16.pdf
2. Madhu Sudan and Shien Jin Ong. Massachusetts Institute of Technology: 6.841/18.405J Advanced Complexity Theory: Lecture 6: Randomized Algorithms, Properties of BPP. February 26, 2003.
3. http://weblog.fortnow.com/2005/12/pulling-out-quantumness.html
4. Adleman, L. M. (1978). «Two theorems on random polynomial time». Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computing. pp. 75–83
5. Bennett, Charles H.; Gill, John (1981). Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1. SIAM Journal on Computing. 10. [S.l.: s.n.] pp. 96–113. ISSN 1095-7111
6. László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson (1993). "BPP has subexponential time simulations unless EXPTIME has publishable proofs". Computational Complexity, 3:307–318.
7. Russell Impagliazzo and Avi Wigderson (1997). "P=BPP if E requires exponential circuits: Derandomizing the XOR Lemma". Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 220–229. doi:10.1145/258533.258590

Bibliografia

• Valentine Kabanets (2003). "CMPT 710 – Complexity Theory: Lecture 16". Simon Fraser University.
• Christos Papadimitriou (1993). Computational Complexity 1st edition ed. [S.l.]: Addison Wesley. ISBN 0-201-53082-1 Pages 257–259 of section 11.3: Random Sources. Pages 269–271 of section 11.4: Circuit complexity.
• Michael Sipser (1997). Introduction to the Theory of Computation. [S.l.]: PWS Publishing. ISBN 0-534-94728-X Section 10.2.1: The class BPP, pp. 336–339.
• Este artigo foi inicialmente traduzido, total ou parcialmente, do artigo da Wikipédia em inglês cujo título é «Bounded-error probabilistic polynomial», especificamente desta versão.

Ligações externas

• Princeton CS 597E: Derandomization paper list (em inglês)
• Harvard CS 225: Pseudorandomness (em inglês)