BPP (complexidade) - BPP (complexity)

Na teoria da complexidade computacional , 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 a 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 tem algoritmos probabilísticos eficientes que podem ser executados rapidamente em máquinas modernas reais. 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.

Algoritmo BPP (1 execução)
Responder produzido Resposta correta	sim	Não
sim	≥ 2/3	≤ 1/3
Não	≤ 1/3	≥ 2/3
Algoritmo BPP ( k execuções)
Responder produzido 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á no BPP se houver um algoritmo para ele que tenha as seguintes propriedades:

É permitido virar moedas e tomar decisões aleatórias
É garantido que funcione em tempo polinomial
Em qualquer execução do algoritmo, ele tem uma probabilidade de no máximo 1/3 de dar a resposta errada, seja 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 é executado para o tempo polinomial em todas as entradas
Para todo x em L , M produz 1 com probabilidade maior ou igual a 2/3
Para todos os x não em L , M produz 1 com probabilidade menor ou igual a 1/3

Ao contrário da classe de complexidade ZPP , a máquina M deve funcionar por tempo polinomial em todas as entradas, independentemente do resultado dos lançamentos aleatórios de moedas.

Alternativamente, o 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 é executado para o tempo polinomial em todas as entradas
Para todo x em L , a fração das strings y de comprimento p (| x |) que satisfazem é maior ou igual a 2/3 ${\ displaystyle M (x, y) = 1}$
Para todos os x não em L , a fração das cordas y de comprimento p (| x |) que satisfazem é menor ou igual a 1/3 ${\ displaystyle M (x, y) = 1}$

Nessa 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, uma vez que 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 mudaria o conjunto resultante BPP . Por exemplo, se alguém definiu a classe com a restrição de que o algoritmo pode estar errado com probabilidade no máximo 1/2 ¹⁰⁰ , isso resultaria na mesma classe de problemas. A probabilidade de erro nem mesmo precisa ser constante: a mesma classe de problemas é definida permitindo erros tão altos quanto 1/2 - n ^{- c} por um lado, ou exigindo erros tão pequenos quanto 2 ^{- n ^c} 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 sujeito a erros muitas vezes e usar a maioria dos resultados das execuções para obter um algoritmo mais preciso. A chance de que a maioria das corridas estejam erradas diminui exponencialmente como consequência do limite de Chernoff .

Problemas

Problema não resolvido na ciência da computação :

${\ displaystyle {\ mathsf {P}} {\ overset {?} {=}} {\ mathsf {BPP}}}$

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

Todos os problemas em P estão obviamente também no BPP . No entanto, muitos problemas têm sido conhecida a estar em BPP , mas não conhecido por ser em P . O número de tais problemas está diminuindo, e conjectura-se que P = BPP .

Por muito tempo, um dos problemas mais famosos que se sabia estar no BPP, mas não se sabia estar em P, era o problema de determinar se um determinado número é primo . No entanto, nos papel 2002 PRIMES está em P , Manindra Agrawal e seus alunos Neeraj Kayal e Nitin Saxena encontrado um algoritmo de tempo polinomial determinista 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 é o teste de identidade polinomial , 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 entrada fornecida, mas não para os coeficientes. Em outras palavras, há uma atribuição de valores às variáveis de forma que quando um polinômio diferente de zero é avaliado nesses valores, o resultado é diferente de zero? É suficiente escolher o valor de cada variável uniformemente ao acaso a partir de um subconjunto finito de pelo menos d valores para atingir a probabilidade de erro limitado, onde d é o grau total do polinômio.

Classes relacionadas

Se o acesso a aleatoriedade é removido da definição de BPP , temos 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 ao BPP , ou permitir que caminhos de computação tenham comprimentos diferentes, fornece o _caminhoBPP da classe . O _caminhoBPP é 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 na classe BPP possuem algoritmos de Monte Carlo com tempo de execução limitado polinomial. Isso é comparado a um algoritmo de Las Vegas, que é um algoritmo aleatório que produz a resposta correta ou "falha" com baixa probabilidade. Algoritmos de Las Vegas com tempos de execução de limite polinomial são usados para definir a classe ZPP . Alternativamente, o 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, uma vez que pode ser executado em tempo superpolinomial, mas com probabilidade muito baixa.

Propriedades teóricas da complexidade

BPP em relação a outras classes de complexidade probabilística ( ZPP , RP , co-RP, BQP , PP ), que generalizam P dentro de PSPACE . Não se sabe se alguma dessas restrições é estrita.

Sabe-se que o BPP é fechado sob complemento ; ou seja, BPP = co-BPP . O BPP é baixo por si só, o que significa que uma máquina BPP com o poder de resolver problemas BPP instantaneamente (uma máquina oráculo BPP ) não é mais poderosa 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 dos dois. Se NP está contido em BPP , que é considerada improvável, uma vez que implicaria soluções práticas para NP-completos problemas, então NP = RP e PH ⊆ BPP .

Sabe-se que RP é um subconjunto do BPP e o BPP é um subconjunto do PP . Não se sabe se esses dois são subconjuntos estritos, já que nem sabemos se P é um subconjunto estrito de PSPACE . O BPP está contido no segundo nível da hierarquia polinomial e, portanto, está contido no PH . Mais precisamente, o teorema de Sipser-Lautemann afirma isso . Como resultado, P = NP leva a P = BPP uma vez que PH colapsa para P neste caso. Assim, P = BPP ou P ≠ NP ou ambos. ${\ displaystyle {\ mathsf {BPP}} \ subseteq \ Sigma _ {2} \ cap \ Pi _ {2}}$

O teorema de Adleman afirma que a participação em qualquer linguagem no BPP pode ser determinada por uma família de circuitos Booleanos de tamanho polinomial , o que significa que o BPP está contido em P / poli . De fato, como consequência da prova desse fato, todo algoritmo BPP operando em entradas de comprimento limitado pode ser desrandomizado em um algoritmo determinístico usando uma sequência fixa de bits aleatórios. Encontrar essa string pode ser caro, no entanto. Alguns resultados de separação fracos para classes de tempo de Monte Carlo foram provados 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 ao oráculos, sabemos que existem oráculos A e B, tal 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 em que BPP = EXP ^NP (e, portanto, P <NP <BPP = EXP = NEXP), que pode ser construído iterativamente como segue. Para um problema completo E ^NP (relativizado) fixo , 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, fixe 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 string de comprimento kn e, em seguida, trate a saída para consultas de comprimento ≤ ( k +1) n como fixas e prossiga com instâncias de comprimento n +1.

Lema: Dado um problema (especificamente, um código de máquina de oráculo 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 fixas) são corrigidas passo a passo. Há no máximo uma consulta ao oráculo por etapa de computação determinística. Para o oráculo NP relativizado, se possível fixe a saída em 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 base por etapa. Uma vez que existem 2 ^{O ( n )} passos, segue-se o lema.

O lema garante que (para um k grande o suficiente ), é possível fazer a construção deixando cadeias de caracteres 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, esta construção é eficaz na medida em que um dado do Oracle Um arbitrária que pode providenciar o oráculo B ter P ^Um ≤P ^B e EXP ^{NP ^A} = EXP ^{NP ^B} = 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 dada.

Desrandomização

A existência de certos geradores de números pseudo-aleatórios fortes é conjecturada pela maioria dos especialistas na área. Esta conjectura implica que a aleatoriedade não dá poder computacional adicional ao cálculo do tempo polinomial, isto é, 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úmero aleatório 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 colapsa para MA , o BPP está contido em

{\ displaystyle {\ textf {io-SUBEXP}} = \ bigcap \ nolimits _ {\ varejpsilon> 0} {\ textf {io-DTIME}} \ left (2 ^ {n ^ {\ varejpsilon}} \ right). }

A classe io-SUBEXP , que significa infinitamente frequentemente SUBEXP , contém problemas que possuem algoritmos de tempo subexponencial para infinitamente muitos 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 , colapsa para E ; no entanto, observe que a hierarquia de tempo exponencial geralmente é conjecturada para não entrar em colapso.

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

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

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

Veja também

Referências

Valentine Kabanets (2003). "CMPT 710 - Teoria da Complexidade: Aula 16". Simon Fraser University .
Christos Papadimitriou (1993). Complexidade computacional (1ª ed.). Addison Wesley. ISBN 0-201-53082-1.Páginas 257–259 da seção 11.3: Fontes aleatórias. Páginas 269-271 da seção 11.4: Complexidade do circuito.
Michael Sipser (1997). Introdução à Teoria da Computação . Publicação PWS. ISBN 0-534-94728-X. Seção 10.2.1: A classe BPP, pp. 336–339.
Karpinski, Marek ; Verbeek, Rutger (1987a). “Aleatoriedade, provabilidade e a separação do tempo e do espaço de Monte Carlo”. Notas de aula em Ciência da Computação . 270 : 189–207.
Karpinski, Marek ; Verbeek, Rutger (1987b). "Sobre as funções construtíveis do espaço de Monte Carlo e resultados de separação para classes de complexidade probabilística" . Informação e computação . 75 (2): 178–189. doi : 10.1016 / 0890-5401 (87) 90057-5 .
Arora, Sanjeev; Boaz Barak (2009). "Complexidade Computacional: Uma Abordagem Moderna".

Languages

In other projects