ZPP (complexidade) - ZPP (complexity)
Na teoria da complexidade , ZPP ( tempo polinomial probabilístico de erro zero ) é a classe de complexidade de problemas para os quais existe uma máquina de Turing probabilística com estas propriedades:
- Ele sempre retorna a resposta SIM ou NÃO correta.
- O tempo de execução é polinomial na expectativa para cada entrada.
Em outras palavras, se o algoritmo puder lançar uma moeda verdadeiramente aleatória enquanto está em execução, ele sempre retornará a resposta correta e, para um problema de tamanho n , há algum polinômio p ( n ) de modo que a média em execução o tempo será menor que p ( n ), embora ocasionalmente possa ser muito mais longo. Esse algoritmo é chamado de algoritmo de Las Vegas .
Alternativamente, ZPP pode ser definido como a classe de problemas para os quais existe uma máquina de Turing probabilística com estas propriedades:
- Sempre é executado em tempo polinomial.
- Ele retorna uma resposta SIM, NÃO ou NÃO SEI.
- A resposta é sempre NÃO SEI ou a resposta correta.
- Ele retorna DO NOT KNOW com probabilidade no máximo 1/2 para cada entrada (e a resposta correta caso contrário).
As duas definições são equivalentes.
A definição de ZPP é baseada em máquinas de Turing probabilísticas, mas, para maior clareza, observe que outras classes de complexidade baseadas nelas incluem BPP e RP . A classe BQP é baseada em outra máquina com aleatoriedade: o computador quântico .
Definição de interseção
A classe ZPP é exatamente igual à interseção das classes RP e co-RP . Freqüentemente, essa é a definição de ZPP . Para mostrar isso, primeira nota que cada problema que está em ambos RP e co-RP tem um algoritmo de Las Vegas da seguinte forma:
- Suponha que temos uma linguagem L reconhecida pelo algoritmo RP A e pelo (possivelmente completamente diferente) algoritmo co-RP B.
- Dada uma entrada, execute A na entrada para uma etapa. Se retornar SIM, a resposta deve ser SIM. Caso contrário, execute B na entrada para uma etapa. Se retornar NÃO, a resposta deve ser NÃO. Se nenhum dos dois ocorrer, repita esta etapa.
Observe que apenas uma máquina pode dar uma resposta errada e a chance dessa máquina dar a resposta errada durante cada repetição é de no máximo 50%. Isso significa que a chance de atingir a k- ésima rodada diminui exponencialmente em k , mostrando que o tempo de execução esperado é polinomial. Isso mostra que RP intersectam co-RP está contido em ZPP .
Para mostrar que ZPP está contido em RP intersectar co-RP , suponha que temos um algoritmo C de Las Vegas para resolver um problema. Podemos então construir o seguinte algoritmo RP :
- Execute C por pelo menos o dobro do tempo de execução esperado. Se der uma resposta, dê essa resposta. Se ele não der nenhuma resposta antes de pará-lo, dê NÃO.
Pela Desigualdade de Markov , a chance de que ela forneça uma resposta antes de pará-la é de pelo menos 1/2. Isso significa que a chance de darmos a resposta errada em uma instância SIM, parando e produzindo NÃO, é no máximo 1/2, se encaixando na definição de um algoritmo RP . O algoritmo co-RP é idêntico, exceto que dá SIM se C "atingir o tempo limite".
Testemunha e prova
As classes NP , RP e ZPP podem ser pensadas em termos de prova de pertencimento a um conjunto.
Definição: um verificador V para um conjunto X é uma máquina de Turing tal que:
- se x está em X, então existe uma string w tal que V ( x , w ) aceita;
- se x não estiver em X , então, para todas as cadeias w , V ( x , w ) rejeita.
A string w pode ser considerada uma prova de filiação. No caso de provas curtas (de comprimento limitado por um polinômio no tamanho da entrada) que podem ser verificadas de forma eficiente ( V é uma máquina de Turing determinística de tempo polinomial), a string w é chamada de testemunha .
Notas:
- A definição é muito assimétrica. A prova de x estar em X é uma única string. A prova de x não estar em X é a coleção de todas as cadeias de caracteres, nenhuma das quais é uma prova de associação.
- A disponibilidade de testemunhas é uniforme. Para todo x em X, deve haver uma testemunha. Não é o caso em que certos x em X são muito difíceis de verificar, ao passo que a maioria não é.
- A testemunha não precisa ser uma prova tradicional. Se V for uma máquina de Turing probabilística que poderia aceitar x se x estiver em X, então a prova é a sequência de cara ou coroa que leva a máquina, por sorte, intuição ou gênio, a aceitar x .
- O co-conceito é uma prova de não adesão, ou adesão ao conjunto complementar.
As classes NP , RP e ZPP são conjuntos que possuem testemunhas de adesão. A classe NP exige apenas que existam testemunhas. Eles podem ser muito raros. Das 2 strings possíveis f (| x |) , com f um polinômio, apenas uma precisa fazer com que o verificador aceite (se x estiver em X. Se x não estiver em X, nenhuma string fará com que o verificador aceite).
Para as classes RP e ZPP, qualquer string escolhida ao acaso provavelmente será uma testemunha.
As co-classes correspondentes têm testemunho de não adesão. Em particular, co-RP é a classe de conjuntos para os quais, se x não estiver em X, qualquer string escolhida aleatoriamente provavelmente será uma testemunha de não pertencimento. ZPP é a classe de conjuntos para os quais qualquer string aleatória provavelmente será uma testemunha de x em X ou x não em X, seja qual for o caso.
Conectar esta definição com outras definições de RP , co-RP e ZPP é fácil. A Máquina de Turing de tempo polinomial probabilística V * w ( x ) corresponde à Máquina de Turing de tempo polinomial determinística V ( x , w ) substituindo a fita aleatória de V * por uma segunda fita de entrada para V na qual está escrita a sequência de cara ou coroa. Ao selecionar a testemunha como uma string aleatória, o verificador é uma Máquina de Turing de tempo polinomial probabilística cuja probabilidade de aceitar x quando x está em X é grande (maior que 1/2, digamos), mas zero se x ∉ X (para RP ); de rejeitar x quando x não está em X é grande, mas zero se x ∈ X (para co-RP ); e aceitar ou rejeitar corretamente x como um membro de X é grande, mas zero de aceitar ou rejeitar x incorretamente (para ZPP ).
Pela seleção aleatória repetida de uma possível testemunha, a grande probabilidade de que uma string aleatória seja uma testemunha fornece um algoritmo de tempo polinomial esperado para aceitar ou rejeitar uma entrada. Por outro lado, se a Máquina de Turing é esperada em tempo polinomial (para qualquer x dado), uma fração considerável das execuções deve ser limitada no tempo polinomial e a sequência de moedas usada em tal execução será uma testemunha.
O ZPP deve ser contrastado com o BPP . A classe BPP não requer testemunhas, embora testemunhas sejam suficientes (portanto, BPP contém RP , co-RP e ZPP ). Um BPP língua tem V (x, w) aceitar em um (claro) maioria das cordas w se x é em X, e inversamente rejeitar em um (claro) maioria das cordas w se x não está presente em X . Nenhuma string w precisa ser definitiva e, portanto, não podem, em geral, ser considerados provas ou testemunhas.
Propriedades teóricas da complexidade
Sabe-se que ZPP é fechado em complemento; ou seja, ZPP = co-ZPP.
O ZPP é baixo para si mesmo, o que significa que uma máquina ZPP com o poder de resolver problemas de ZPP instantaneamente (uma máquina oracle ZPP) não é mais poderosa do que a máquina sem esse poder extra. Em símbolos, ZPP ZPP = ZPP .
ZPP NP BPP = ZPP NP .
NP BPP está contido em ZPP NP .
Conexão com outras classes
Uma vez que ZPP = RP ∩ coRP , ZPP está obviamente contido em RP e coRP .
A classe P está contida no ZPP , e alguns cientistas da computação conjeturaram que P = ZPP , ou seja, todo algoritmo de Las Vegas tem um equivalente de tempo polinomial determinístico.
Existe um oráculo relativo ao qual ZPP = EXPTIME . Uma prova para ZPP = EXPTIME implicaria que P ≠ ZPP , como P ≠ EXPTIME (ver teorema da hierarquia de tempo ).