Mostrar código-fonte de BPP

{{Ver desambig|o banco|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 [[Complexidade de tempo#Tempo Polinomial|tempo polinomial]], com uma [[probabilidade]] de erro de no máximo 1/3 para todas as instâncias.

{| class="wikitable" style="float:right; text-align:center; margin: 1em 0 1em 1em;"
|-
!colspan="3"|Algoritmo BPP (1 execução)
|-
|
|colspan="2"|Resposta produzida
|-
| Reposta<br />correta
| SIM
| NÃO
|-
| SIM
| ≥ 2/3
| ≤ 1/3
|-
| NÃO
| ≤ 1/3
| ≥ 2/3
|-
!colspan="3"|Algoritmo BPP (''k'' execuções)
|-
|
|colspan="2"|Resposta produzida
|-
| Resposta<br />correta
| SIM
| NÃO
|-
| SIM
| > 1 − 2<sup>−''ck''</sup>
| < 2<sup>−''ck''</sup>
|-
| NÃO
| < 2<sup>−''ck''</sup>
| > 1 − 2<sup>−''ck''</sup>
|-
|colspan="3" style="font-size:85%"|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 [[algoritmo probabilístico|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 matemática|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''<sup>−''c''</sup> por um lado, ou exigir erros tão pequenos quanto 2<sup>−''n<sup>c</sup>''</sup> 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 [[decaimento exponencial|decai exponencialmente]] como consequência do [[Limite de Chernoff]].<ref>http://www.cs.sfu.ca/~kabanets/cmpt710/lec16.pdf</ref> 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<sup>100</sup>, 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 ==
{{unsolved|ciência da computação|'''P''' {{=}} '''BPP''' ?}}
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 [[teste de primalidade|determinar]] se um dado número é [[número primo|primo]]. Contudo, na documentação de 2002 ''[[Teste de primalidade AKS|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 [[RP (complexidade)|co-RP]]) que ainda não se sabe se está em '''P''' é o [[teste polinomial de identidade]], é o problema de determinar se um [[Função polinomial|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.<ref>Madhu Sudan and Shien Jin Ong. Massachusetts Institute of Technology: 6.841/18.405J Advanced Complexity Theory: [http://people.csail.mit.edu/madhu/ST03/scribe/lect06.pdf Lecture 6: Randomized Algorithms, Properties of BPP]. February 26, 2003.</ref>

== 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 (complexidade)|baixa]] por si mesma, significando que a máquina '''BPP''' com o poder de resolver problemas '''BPP''' instantaneamente (uma '''BPP''' [[Máquina Oráculo|máquina oráculo]]) não é mais poderosa que a máquina sem essa poder extra. Em símbolos, '''BPP'''<sup>'''BPP'''</sup> = '''BPP'''.

O relacionamento entre '''BPP''' e '''[[NP (complexidade)|NP]]''' é desconhecido: não se sabe se '''BPP''' é um [[subconjunto]] de '''[[NP (complexidade)|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 (complexidade)|PH]]''' ⊆ '''BPP'''.<ref>http://weblog.fortnow.com/2005/12/pulling-out-quantumness.html</ref>

Sabe-se que '''RP''' é um subconjunto de '''BPP''', e '''BPP''' é um subconjunto de '''[[PP (complexidade)|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''' ⊆ Σ<sub>2</sub> ∩ Π<sub>2</sub>. 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 [[circuito booleano|circuitos booleanos]] de tamanho polinomial, o que significa que '''BPP''' está contido em '''[[P/poly]]'''.<ref>{{citar conferência|autor=Adleman, L. M.|título=Two theorems on random polynomial time|títulolivro=Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computing|data=1978| páginas=75–83}}</ref> 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'''<sup>A</sup> = '''BPP'''<sup>A</sup> e '''P'''<sup>B</sup> ≠ '''BPP'''<sup>B</sup>. 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'''.<ref>{{citar livro|sobrenome1=Bennett|nome1=Charles H.|sobrenome2=Gill|nome2=John|título=Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1|ano=1981|jornal=SIAM Journal on Computing|issn=1095-7111|volume=10|número=1| páginas=96–113}}</ref>

== Desaleatorização ==
A existência de certos fortes [[gerador de números pseudoaleatórios|geradores de números pseudoaleatórios]] é [[conjectura]]do 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 [[Complexidade_de_tempo#Tempo_exponencial|EXPTIME]] entre em colapso para '''[[MA (complexidade)|MA]]''', '''BPP''' está contido em '''i.o.-SUBEXP''' = <math>\bigcap_{\varepsilon>0}\hbox{i.o.-DTIME}(2^{n^\varepsilon})</math>.<ref name="Babai">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.</ref> A classe '''i.o.-SUBEXP''' (inglês: infinitely often SUBEXP, frequentemente infinitamente SUBEXP, contêm problemas que possuem algoritmos de [[Complexidade_de_tempo#Tempo_Sub-exponencial|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|hierarquia polinomial]] e '''E''' como '''E<sup>PH</sup>''', 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 [[Complexidade exponencial|E]], onde <math>\textrm{E}=\textrm{DTIME} \left( 2^{O(n)} \right)</math>, possui complexidade de circuito <math>2^{\Omega(n)}</math> então '''P''' = '''BPP'''.<ref>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}}</ref>

{{referências}}

== Bibliografia ==
* Valentine Kabanets (2003). "CMPT 710 – Complexity Theory: Lecture 16". [[Simon Fraser University]].
* {{citar livro|autor = [[Christos Papadimitriou]] | ano = 1993 | título = Computational Complexity | editora = Addison Wesley |edição= 1st edition | isbn = 0-201-53082-1}} Pages 257–259 of section 11.3: Random Sources. Pages 269–271 of section 11.4: Circuit complexity.
* {{citar livro|autor = [[Michael Sipser]] | ano = 1997 | título = Introduction to the Theory of Computation | editora = PWS Publishing | isbn = 0-534-94728-X}} Section 10.2.1: The class BPP, pp.&nbsp;336–339.
{{tradução/ref|en|Bounded-error probabilistic polynomial|oldid=432055826}}

== Ligações externas ==
* [http://www.cs.princeton.edu/courses/archive/fall03/cs597E/ Princeton CS 597E: Derandomization paper list] {{en}}
* [http://www.courses.fas.harvard.edu/~cs225/ Harvard CS 225: Pseudorandomness] {{en}}

{{Classes de complexidade}}
[[Categoria:Classes de complexidade]]
[[Categoria:Aleatoriedade]]