Em que classe são algoritmos aleatórios que erram com exatamente 25% de chance?

17

Suponha que eu considere a seguinte variante do BPP, que vamos chamar de BPP E (xact): Um idioma está no EBPP se houver um TG aleatório polinomial no tempo que aceite todas as palavras da linguagem com exatamente 3/4 de probabilidade e todas as palavras que não estejam em o idioma com exatamente 1/4 de probabilidade. Obviamente, o EBPP está contido no BPP, mas eles são iguais? Isso foi estudado? E o ERP igualmente definido?

Motivação. Minha principal motivação é que eu queria saber qual é o algoritmo teórico da complexidade do algoritmo aleatório `` correto no valor esperado '' de Faenza et al. (consulte http://arxiv.org/abs/1105.4127 ). Primeiro, eu queria entender quais problemas de decisão esse algoritmo pode resolver (com o pior caso de tempo de execução polinomial). Vamos denotar essa classe por E (xpected) V (alue) PP. É fácil ver que USAT EVPP. Também é fácil ver esse EBPP EVPP. Então essa foi minha motivação. Qualquer comentário sobre o EVPP também é bem-vindo.

De fato, seu algoritmo sempre gera um número não negativo. Se representarmos as decisões problemas reconhecível por tal algoritmo por EVP (ositive) PP, então ainda temos USAT EVPPP. Embora o EBPP possa não ser um subconjunto do EVPPP, temos o ERP EVPPP. Talvez usando isso, possamos definir uma classificação (não-negativa) para problemas de decisão.

domotorp
fonte
10
Eu acho que você já percebe isso, mas se você relaxar a restrição às palavras aceitar na língua com probabilidade 3/4±ε para ε1 1/poli(n) , em seguida, as classes devem ser iguais.
Huck Bennett #
3
@domotorp Qual é a motivação por trás dessa pergunta? O que você pretende fazer com essa classe de complexidade semântica? Você vê uma maneira de usar a EBPP em algum lugar para provar um teorema? Você pode elaborar?
Tayfun Pay
11
Veja o artigo "Probabilistic Complexity Classes and Lowness", de Uwe Schoning, 1989.
Tayfun Pay
11
@ Tayfun: Eu verifiquei, mas não consegui encontrar nada relevante. Você poderia ser mais específico?
Domotorp #
2
@HuckBennett: ou mesmo para £ exp ( - p o l y ( n ) ) . 3/4±ϵϵexp(-poeuy(n))
Colin McQuillan

Respostas:

10

Em uma nota lateral, não está claro que o EBPP seja uma classe robusta. Por exemplo, se em vez de permitir que o algoritmo jogue uma moeda imparcial, se lhe for dada uma moeda imparcial de 3 lados ou um dado de 6 lados, não está claro que você recebe a mesma classe. O BPP permanece o mesmo se você alterar esses detalhes.

Enfim, sua principal pergunta é se o EBPP é igual ao BPP ou não. Parece-me que o EBPP está mais próximo de P do que de BPP. Considere a complexidade da consulta ou a versão oracle dessas classes, onde elas têm acesso a uma grande string de entrada e precisam fazer consultas para aprender bits dessa string. Se você tem um algoritmo P que computa uma função com Q consultas, então existe uma exata representação polinômio de grau Q para f sobre R . (Esse é o argumento do método polinomial usual.) Por outro lado, se você tiver um algoritmo BPP, obterá um polinômio Q de grau sobre R que se aproxima de ffQQfRQRfno sentido de que seu valor é próximo ao valor de em cada entrada.f

Dado um algoritmo EBPP para uma função , podemos construir um polinômio que produz 1/4 quando a resposta é NÃO e 3/4 quando a resposta é SIM. Subtraindo 1/2 e multiplicando por 2, é possível obter um polinômio exato, exatamente como no caso de P. Isso sugere para mim que o EBPP está mais próximo de P.f

Esta observação também pode ser usada para mostrar uma separação do oráculo entre EBPP e BPP. Considere o problema da maioria da promessa em que você promete que a entrada tem mais de 2N / 3 1s ou menos que N / 3 1s e você precisa decidir qual é o caso. Isso está claramente no BPP. Usando o argumento polinomial descrito acima, pode ser demonstrado que esta função requer consultas para uma máquina EBPP. Mas observe que você também pode provar uma separação do oráculo de outra maneira, entre P e EBPP. Então, talvez os resultados da Oracle não digam muito sobre esse problema? Ou talvez o que eles dizem é que será difícil mostrar igualdade em qualquer direção.Ω(N)

Robin Kothari
fonte
11
Sim, a separação do oráculo parece bem direta nos dois casos.
Domotorp 7/12
1

Em relação às separações de oráculos, há um oráculo com EBPP = BPP = EXP NP e um oráculo com P = ⊕P (e, portanto, EBPP = P) e BPP = EXP NP .

Uma construção do BPP = EXP NP oracle (incluindo a do artigo da BPP wikipedia ) é escolher um problema completo EXP NP relativizado e prosseguir recursivamente no tamanho da entrada (para esse problema), corrigir resultados para instâncias de problemas desse tamanho e em seguida, forneça respostas para esse problema se for consultado com a entrada e um preenchimento (de comprimento apropriado) que não foi corrigido. Para EBPP = EXP NP , em vez de quase sempre fornecer as respostas corretas, podemos fornecer respostas erradas apenas o suficiente para tornar as contagens exatamente corretas. Há também um oráculo no qual o análogo de erro zero do EBPP (exatamente 1/2 probabilidade de relatar falha) é igual a EXP (e um oráculo com P = ⊕P mas ZPP = EXP).

O oráculo P = ⊕P e BPP = EXP NP é anotado aqui .

Além de estar no BPP e em C = P, o EBPP está em ⊕P, pois podemos reduzir a probabilidade ao número de testemunhas e depois ajustá-lo.

No mundo não relativizado, o BPP provavelmente é igual a P, mas a evidência é ainda mais forte para o EBPP. O EBPP depende do número exato de caminhos de uma maneira que, a menos que um cancelamento inesperado ocorra, pareça essencialmente impossível de explorar.

Dmytro Taranovsky
fonte
0

Esta é uma resposta parcial; talvez isso inspire outra pessoa a oferecer uma melhor.

A sua classe é um caso especial de C = P . Eu acho que uma maneira de definir C = P é a seguinte (consulte a Seção 2 deste documento ). Uma linguagem L está em C = P se houver um verificador de tempo polinomial V tal queEBPPC=PC=PLC=PV

  • se estiver em L , então Pr w [ V ( x , w )  aceita ] = 3xL ePrw[V(x,w) accepts]=34
  • se não estiver em L , então Pr w [ V ( x , w )  aceita ] 3xL .Prw[V(x,w) accepts]34

(A probabilidade de completude pode ser essencialmente qualquer fração fixa; escolhi para que corresponda à probabilidade fornecida na sua pergunta.)34

Uma maneira de definir é a seguinte. Uma linguagem L está em E B P P se houver um verificador de tempo polinomial V tal queEBPPLEBPPV

  • se estiver em L , então Pr w [ V ( x , w )  aceita ] = 3xL ePrw[V(x,w) accepts]=34
  • se não estiver em L , então Pr w [ V ( x , w )  aceita ] = 1xL .Prw[V(x,w) accepts]=14
argentpepper
fonte
3
É também um caso especial de BPP.
Peter Shor
@argentpepper O que você acredita ser um caso especial de não parece estar correto. Todas as máquinas C = P precisam aceitar OU rejeitar para todas as entradas. O que você está descrevendo é uma máquina categórica - classe de complexidade semântica. Não aceita nem rejeita se a probabilidade é 1/2? Isso não pode ser uma máquina C = P. C=PC=PC=P
Tayfun Pay
@PeterShor Exatamente
Tayfun Pay
11
@TayfunPay Não acho que seu comentário faça sentido. é um conjunto de idiomas, não máquinas, portanto não existe uma máquina C = P. argentpepper é certo que EBPP é, de facto, um subconjunto de C = P . é só que não é claro se esta inclusão é útil, especialmente desde C = P é uma classe poderosaC=PC=PC=PC=P
Sasho Nikolov
Apenas fornecer uma outra maneira de olhar o problema ...
argentpepper