Resultados da pesquisa - BPP

BPP

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.

{| class="wikitable" style="float:right; text-align:center; margin: 1em 0 1em 1em;" |- !colspan="3"|Algoritmo BPP (1 execução) |- | |colspan="2"|Resposta produzida |- | Reposta
correta | SIM | NÃO |- | SIM | ≥ 2/3 | ≤ 1/3 |- | NÃO | ≤ 1/3 | ≥ 2/3 |- !colspan="3"|Algoritmo BPP (''k'' execuções) |- | |colspan="2"|Resposta produzida |- | Resposta
correta | SIM | NÃO |- | SIM | > 1 − 2^−''ck'' | < 2^−''ck'' |- | NÃO | < 2^−''ck'' | > 1 − 2^−''ck'' |- |colspan="3" style="font-size:85%"|para alguma constante ''c'' > 0 |}

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. Fornecido pela Wikipedia