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. Os algoritmos de Las Vegas foram introduzidos por László Babai , em 1979, sob o contexto do problema do isomorfismo de grafos, como um dual dos Algoritmos de Monte Carlo. Os algoritmos de Las Vegas podem ser utilizados em situações onde o número de soluções possíveis é relativamente limitada, e onde verificar a corretude de uma solução candidata é relativamente fácil, enquanto realmente calcular uma solução é complexo. O nome refere-se à cidade de Las Vegas, Nevada, que é bem conhecida nos Estados Unidos como um ícone dos jogos de azar.