BPP
Da Wikipédia, a enciclopédia livre
Da Wikipédia, a enciclopédia livre
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:
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/2100, isso resultaria em uma mesma classe de problemas.
Uma linguagem L está na BPP se e somente se existe uma máquina de Turing probabilística, tal que:
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:
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.
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 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]
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.
É 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, BPPBPP = 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 ⊆ Σ2 ∩ Π2. 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 PA = BPPA e PB ≠ BPPB. 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]
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 = .[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 EPH, 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 , possui complexidade de circuito então P = BPP.[7]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.