BPP
De Wikipedia, a enciclopédia encyclopedia
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.
Mais informação Algoritmo BPP (1 execução), Algoritmo BPP (k execuções) ...
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 |
Fechar
Informalmente, um problema está em BPP se existe um algoritmo para ele que tenha as seguintes propriedades:
- É permitido "jogar moedas" e fazer decisões aleatórias
- É garantido que será executado em tempo polinomial
- Em qualquer dada execução do algoritmo, o mesmo tem a probabilidade de no máximo 1/3 de fornecer uma resposta errada, se a resposta for SIM ou NÃO.