Algoritmo de Las Vegas
Em computação, um algoritmo de Las Vegas é um algoritmo aleatório que devolve sempre resultados corretos; isto é, ele produz sempre o resultado correto ou informa sobre a falha. Em outras palavras, um algoritmo de Las Vegas não aposta com a corretude do resultado; ele aposta somente com os recursos usados para a computação. Um exemplo simples é o algoritmo aleatório quicksort, onde o pivô é escolhido aleatoriamente, mas o resultado é sempre ordenado. A usual definição de um algoritmo de Las Vegas inclui a restrição de que o tempo de execução esperado tem sempre que ser finito, quando a estimativa é calculada em um espaço de informações aleatórias, ou entropia, utilizados no algoritmo. Uma definição alternativa requer que um algoritmo de Las Vegas pare sempre que seja eficaz, mas ele pode dar como saída um símbolo que não faz parte do espaço de solução para indicar a falha em encontrar uma solução.
Imagem: ArturoRosillo · BY-NC · Openverse
A classe de complexidade dos problemas de decisão que possuem algoritmos de Las Vegas com tempo de execução estimado polinomial é ZPP. Acontece que Z P P = R P ∩ c o − R P {\displaystyle ZPP=RP\cap co-RP} , o que está intimamente ligado com a forma que os algoritmos de Las Vegas são, às vezes, construídos. Ou seja, a classe RP consiste em todos os problemas de decisão para os quais existe um algoritmo aleatório de tempo polinomial onde a resposta correta é "não", mas é permitido estar errado, com uma certa probabilidade (limitada até 1), quando a resposta é "sim". Quando existe um algoritmo para um problema e o seu complemento (com as respostas "sim" e "não" trocadas), os dois algoritmos podem ser executados simultaneamente e repetidamente: execute cada um para um número constante de passos, revezando entre eles, até que um deles retorne uma resposta definitiva. Esta é a forma padrão para a construção de um algoritmo de Las Vegas que se espera ser executado em tempo polinomial. Note que, em geral, não há um limite superior do pior caso sobre o tempo de execução de um algoritmo de Las Vegas.
Os algoritmos de Las Vegas podem ser contrastados com os algoritmos de Monte Carlo, em que os recursos são limitados, mas a resposta não é garantida de sempre ser correta. Via uma aplicação da Desigualdade de Markov , um algoritmo de Las Vegas pode ser convertido em um algoritmo de Monte Carlo via rescisão antecipada.
