BPP (complexidade)

Na teoria da complexidade computacional, um ramo da ciência da computação, tempo polinomial probabilístico de erro limitado (BPP) é a classe de problemas de decisão solucionáveis por uma máquina de Turing probabilística em tempo polinomial com uma probabilidade de erro limitada por 1/3 para todas as instâncias. BPP é uma das maiores classes práticas de problemas, o que significa que a maioria dos problemas de interesse em BPP possui algoritmos probabilísticos eficientes que podem ser executados rapidamente em máquinas modernas. BPP também contém P, a classe de problemas solucionáveis em tempo polinomial com uma máquina determinística, uma vez que uma máquina determinística é um caso especial de uma máquina probabilística.

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

• É permitido virar moedas e tomar decisões aleatórias
• É garantido correr em tempo polinomial
• Em qualquer execução dada do algoritmo, ele tem uma probabilidade de no máximo 1/3 de dar a resposta errada, se a resposta é SIM ou NÃO.

Definição

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

• M corre para o tempo polinomial em todas as entradas
• Para todos x em L, M saídas 1 com probabilidade maior ou igual a 2/3
• Para todos x Não. L, M saídas 1 com probabilidade inferior ou igual a 1/3

Ao contrário da classe de complexidade ZPP, a máquina M é necessária para executar em tempo polinomial em todas as entradas, independentemente do resultado das jogadas aleatórias de moeda.

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

• M corre para o tempo polinomial em todas as entradas
• Para todos x em L, a fração de strings Sim. de comprimento p(em inglês)x|) que satisfazem M(x,Sim.)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1(x,y)=1} é maior ou igual a 2/3
• Para todos x Não. L, a fração de strings Sim. de comprimento p(em inglês)x|) que satisfazem M(x,Sim.)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1(x,y)=1} é inferior ou igual a 1/3

Nesta definição, a string y corresponde à saída dos lançamentos aleatórios de moeda que a máquina de Turing probabilística teria feito. Para algumas aplicações, esta definição é preferível, pois não menciona máquinas de Turing probabilísticas.

Na prática, uma probabilidade de erro de 1/3 pode não ser aceitável, no entanto, a escolha de 1/3 na definição é arbitrária. Modificar a definição para usar qualquer constante entre 0 e 1/2 (exclusivo) no lugar de 1/3 não alteraria o conjunto resultante BPP. Por exemplo, se definirmos a classe com a restrição de que o algoritmo pode estar errado com probabilidade de no máximo 1/2¹⁰⁰, isso resultaria na mesma classe de problemas. A probabilidade de erro nem precisa ser constante: a mesma classe de problemas é definida permitindo erros tão altos quanto 1/2 − n^−c por um lado, ou exigindo um erro tão pequeno quanto 2^−nc por outro lado, onde c é qualquer constante positiva e n é o comprimento da entrada. Essa flexibilidade na escolha da probabilidade de erro é baseada na ideia de executar um algoritmo propenso a erros várias vezes e usar o resultado da maioria das execuções para obter um algoritmo mais preciso. A chance de que a maioria das execuções esteja errada cai exponencialmente como consequência do limite de Chernoff.

Problemas

Todos os problemas em P obviamente também estão em BPP. No entanto, sabe-se que muitos problemas estão em BPP, mas não em P. O número de tais problemas está diminuindo, e conjectura-se que P = BPP.

Durante muito tempo, um dos problemas mais famosos conhecidos por estar em BPP, mas não em P, era o problema de determinar se um determinado número é melhor. No entanto, no artigo de 2002 PRIMES está em P, Manindra Agrawal e seus alunos Neeraj Kayal e Nitin Saxena encontraram um algoritmo determinístico de tempo polinomial para este problema, mostrando assim que ele está em P.

Um exemplo importante de um problema em BPP (na verdade em co-RP) ainda não conhecido por estar em P é a identidade polinomial teste, o problema de determinar se um polinômio é identicamente igual ao polinômio zero, quando você tem acesso ao valor do polinômio para qualquer dado de entrada, mas não aos coeficientes. Em outras palavras, existe uma atribuição de valores às variáveis de modo que, quando um polinômio diferente de zero é avaliado nesses valores, o resultado seja diferente de zero? Basta escolher o valor de cada variável de maneira uniforme e aleatória de um subconjunto finito de pelo menos d valores para alcançar a probabilidade de erro limitada, onde d é o grau total de o polinômio.

Aulas relacionadas

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

Adicionar pós-seleção a BPP, ou permitir caminhos de computação com comprimentos diferentes, dá à classe BPP_caminho. BPP_caminho é conhecido por conter NP e está contido em sua contraparte quântica PostBQP.

Um algoritmo de Monte Carlo é um algoritmo aleatório que provavelmente está correto. Os problemas da classe BPP possuem algoritmos de Monte Carlo com tempo de execução polinomial limitado. Isso é comparado a um algoritmo de Las Vegas, que é um algoritmo aleatório que gera a resposta correta ou "falha" com baixa probabilidade. Algoritmos de Las Vegas com tempos de execução limitados por polinômios são usados para definir a classe ZPP. Alternativamente, ZPP contém algoritmos probabilísticos que estão sempre corretos e têm tempo de execução polinomial esperado. Isso é mais fraco do que dizer que é um algoritmo de tempo polinomial, pois pode ser executado em tempo superpolinomial, mas com probabilidade muito baixa.

Propriedades teóricas de complexidade

BPP em relação a outras classes de complexidade probabilística (ZPP, RP, co-RP, BQP, PP), que generalizam P dentro da PSPACE. É desconhecido se alguma dessas contenção é rigorosa.

Inclusões de classes de complexidade, incluindo P, NP, co-NP, BPP, P/poli, PH e PSPACE

Sabe-se que BPP é fechado sob complemento; ou seja, BPP = co-BPP. BPP é baixo por si só, o que significa que uma máquina BPP com o poder de resolver problemas BPP instantaneamente (um BPP oracle machine) não é mais poderoso do que a máquina sem esse poder extra. Em símbolos, BPP^BPP = BPP.

A relação entre BPP e NP é desconhecida: não se sabe se BPP é um subconjunto de NP, NP é um subconjunto de BPP ou nenhum. Se NP estiver contido em BPP, o que é considerado improvável, pois implicaria em soluções práticas para problemas NP-completos, então NP = RP e PH ⊆ BPP.

Sabe-se que RP é um subconjunto de BPPe BPP é um subconjunto de PP. Não se sabe se esses dois são subconjuntos rigorosos, já que nem sabemos se P é um subconjunto rigoroso 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 afirma que BPP⊆ ⊆ Σ Σ 2─ ─ D D 2{displaystyle {mathsf {BPP}}subseteq Sigma _{2}cap Pi _{2}}. Como resultado, P = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = PN para a P = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = BPP desde então PH colapsos para P Neste caso. Assim como P = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = BPP ou P ≠ PN ou ambos.

O teorema de Adleman afirma que a participação em qualquer linguagem em BPP pode ser determinada por uma família de circuitos booleanos de tamanho polinomial, o que significa que BPP está contido em P/poli. De fato, como consequência da prova deste fato, todo algoritmo BPP operando em entradas de comprimento limitado pode ser desrandomizado em um algoritmo determinístico usando uma cadeia fixa de bits aleatórios. Encontrar essa string pode ser caro, no entanto. Alguns resultados fracos de separação para as classes de tempo de Monte Carlo foram comprovados por Karpinski & Verbeek (1987a), ver também Karpinski & Verbeek (1987b).

Propriedades de fechamento

A classe BPP é fechada em complementação, união e interseção.

Relativização

Em relação aos oráculos, sabemos que existem os oráculos A e B, tais que P^A = BPP^A e P^B ≠ BPP^B. Além disso, em relação a um oráculo aleatório com probabilidade 1, P = BPP e BPP está estritamente contido em NP e co-NP.

Existe até um oráculo no qual BPP=EXP^NP (e, portanto, P<NP<BPP=EXP=NEXP), que pode ser construído iterativamente da seguinte maneira. Para um problema completo fixo E^NP (relativizado), o oráculo dará respostas corretas com alta probabilidade se consultado com a instância do problema seguida por uma string aleatória de comprimento kn (n é o comprimento da instância; k é uma pequena constante apropriada). Comece com n=1. Para cada instância do problema de comprimento n corrija as respostas do oráculo (veja o lema abaixo) para corrigir a saída da instância. Em seguida, forneça as saídas de instância para consultas que consistem na instância seguida por kn-string de comprimento e, em seguida, trate a saída para consultas de comprimento ≤(k+1) n como fixo e prossiga com instâncias de comprimento n+1.

Lema: Dado um problema (especificamente, um código de máquina oracular e restrição de tempo) em E^NP relativizado, para cada oráculo parcialmente construído e entrada de comprimento n, a saída pode ser corrigida especificando 2^O(n) respostas do oráculo.
Prova: A máquina é simulada e as respostas do oráculo (que ainda não foram corrigidas) são corrigidas passo a passo. Há no máximo uma consulta do oráculo por etapa de computação determinística. Para o oráculo NP relativizado, se possível, corrija a saída para sim, escolhendo um caminho de computação e fixando as respostas do oráculo base; caso contrário, nenhuma fixação é necessária e, de qualquer forma, há no máximo 1 resposta do oráculo básico por etapa. Como existem 2 etapas^O(n), o lema segue.

O lema garante que (para um k grande o suficiente), é possível fazer a construção deixando strings suficientes para as respostas E^NP relativizadas. Além disso, podemos garantir que para o E^NP relativizado, o tempo linear é suficiente, mesmo para problemas de função (se dado um oráculo de função e tamanho de saída linear) e com probabilidade de erro exponencialmente pequena (com expoente linear). Além disso, essa construção é eficaz porque, dado um oráculo A arbitrário, podemos organizar o oráculo B para ter P^A≤P^B e EXP^NPA =EXP^NPB=BPP^B. Além disso, para um oráculo ZPP=EXP (e, portanto, ZPP=BPP=EXP<NEXP), deve-se fixar as respostas no cálculo E relativizado para uma não-resposta especial, garantindo assim que nenhuma resposta falsa seja fornecida.

Desaleatorização

A existência de certos geradores de números pseudoaleatórios fortes é conjecturada pela maioria dos especialistas da área. Esta conjectura implica que a aleatoriedade não dá poder computacional adicional à computação em tempo polinomial, ou seja, P = RP = BPP. Observe que geradores comuns não são suficientes para mostrar esse resultado; qualquer algoritmo probabilístico implementado usando um gerador de números aleatórios típico sempre produzirá resultados incorretos em certas entradas, independentemente da semente (embora essas entradas possam ser raras).

László Babai, Lance Fortnow, Noam Nisan e Avi Wigderson mostraram que, a menos que EXPTIME caia para MA, BPP está contido em

0}{textsf {i.o.-DTIME}}left(2^{n^{varepsilon }}right).}" xmlns="http://www.w3.org/1998/Math/MathML">I.o.-SUBEXP= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =⋂ ⋂ ε ε >0I.o.-DTIME(2nε ε ).{displaystyle {textsf {i.o.-SUBEXP}}=bigcap nolimits _{varepsilon >0}{textsf {i.o.-DTIME}}left(2^{n^{varepsilon }}right). ?0}{textsf {i.o.-DTIME}}left(2^{n^{varepsilon }}right).}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f52790872474726ec0b3d32fcbe760d5bfcfafac" style="vertical-align: -1.838ex; width:40.298ex; height:4.843ex;"/>

A classe i.o.-SUBEXP, que significa infinitamente frequente SUBEXP, contém problemas que possuem algoritmos de tempo subexponencial para infinitos tamanhos de entrada. Eles também mostraram que P = BPP se a hierarquia de tempo exponencial, que é definida em termos da hierarquia polinomial e E como E^PH, recolhe para E; no entanto, observe que a hierarquia de tempo exponencial geralmente é considerada não para entrar em colapso.

Russell Impagliazzo e Avi Wigderson mostraram que se houver algum problema em E, onde

E= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =DTEu...ME(2O(n)),{displaystyle {mathsf {E}}={mathsf {DTIME}}left(2^{O(n)}right),}

tem complexidade de circuito 2^Ω(n) então P = BPP.