b'\n_START_ARTICLE_\nAlgoritmo Las Vegas\n_START_PARAGRAPH_\nEm computa\xc3\xa7\xc3\xa3o, um algoritmo Las Vegas \xc3\xa9 um algoritmo rand\xc3\xb4mico\xc2\xa0que sempre retorna resultados\xc2\xa0corretos; isto \xc3\xa9, ele sempre produz o resultado correto ou informa sobre a falha. Em outras palavras, um algoritmo de Las Vegas n\xc3\xa3o aposta com a corretude do resultado; ele aposta somente com os recursos usados para a computa\xc3\xa7\xc3\xa3o. Um exemplo simples \xc3\xa9 o algoritmo rand\xc3\xb4mico\xc2\xa0quicksort, onde o piv\xc3\xb4 \xc3\xa9 escolhido aleatoriamente, mas o resultado \xc3\xa9 sempre ordenado. A usual defini\xc3\xa7\xc3\xa3o de um algoritmo\xc2\xa0Las Vegas inclui a restri\xc3\xa7\xc3\xa3o de que o tempo de execu\xc3\xa7\xc3\xa3o\xc2\xa0esperado tem\xc2\xa0sempre que ser finito, quando a estimativa \xc3\xa9 calculada em um espa\xc3\xa7o de informa\xc3\xa7\xc3\xb5es aleat\xc3\xb3rias, ou entropia, utilizados no algoritmo. Uma defini\xc3\xa7\xc3\xa3o alternativa requer que um algoritmo Las Vegas sempre pare(que seja\xc2\xa0eficaz), mas ele pode dar como sa\xc3\xadda um s\xc3\xadmbolo que n\xc3\xa3o faz parte do espa\xc3\xa7o de solu\xc3\xa7\xc3\xa3o para indicar a falha em encontrar uma solu\xc3\xa7\xc3\xa3o._NEWLINE_Os algoritmos Las Vegas foram introduzidos por L\xc3\xa1szl\xc3\xb3 Babai, em 1979, sob o contexto do problema do isomorfismo de grafos, como um dual dos\xc2\xa0Algoritmos Monte Carlo.\xc2\xa0Os algoritmos\xc2\xa0Las Vegas podem ser utilizados em situa\xc3\xa7\xc3\xb5es onde o n\xc3\xbamero de solu\xc3\xa7\xc3\xb5es poss\xc3\xadveis \xc3\xa9 relativamente limitada, e onde verificar a corretude de uma solu\xc3\xa7\xc3\xa3o candidata \xc3\xa9 relativamente f\xc3\xa1cil, enquanto realmente calcular uma solu\xc3\xa7\xc3\xa3o \xc3\xa9 complexo._NEWLINE_O nome refere-se \xc3\xa0 cidade de\xc2\xa0Las Vegas, Nevada, que \xc3\xa9 bem conhecida nos Estados Unidos como um \xc3\xadcone dos jogos de azar.\n_START_SECTION_\nClasse de complexidade\n_START_PARAGRAPH_\nA classe de complexidade dos problemas de decis\xc3\xa3o que possuem algoritmos Las Vegas com tempo de execu\xc3\xa7\xc3\xa3o estimado polinomial \xc3\xa9 ZPP._NEWLINE_Acontece que o que est\xc3\xa1 intimamente ligado com a forma que os algoritmos Las Vegas s\xc3\xa3o, \xc3\xa0s vezes, constru\xc3\xaddos. Ou seja, a classe RP consiste em todos os problemas de decis\xc3\xa3o para os quais existe um algoritmo rand\xc3\xb4mico de tempo polinomial onde a resposta correta \xc3\xa9 "n\xc3\xa3o", mas \xc3\xa9 permitido estar errado, com uma certa probabilidade (limitada at\xc3\xa9 1), quando a resposta \xc3\xa9 "sim". Quando existe um algoritmo para um problema e o seu complemento (com as respostas "sim" e "n\xc3\xa3o" trocadas), os dois algoritmos podem ser executados simultaneamente e repetidamente: execute cada um para um n\xc3\xbamero constante de passos, revezando entre eles, at\xc3\xa9 que um deles retorne uma resposta definitiva. Esta \xc3\xa9 a forma padr\xc3\xa3o para a constru\xc3\xa7\xc3\xa3o de um algoritmo de Las Vegas que se espera ser executado em tempo polinomial. Note que, em geral, n\xc3\xa3o h\xc3\xa1 um limite superior do pior caso sobre o tempo de execu\xc3\xa7\xc3\xa3o de um algoritmo de Las Vegas.\n_START_SECTION_\nRela\xc3\xa7\xc3\xa3o com os Algoritmos Monte Carlo\n_START_PARAGRAPH_\nOs algoritmos Las Vegas podem ser contrastados com os\xc2\xa0algoritmos Monte Carlo, em que os recursos s\xc3\xa3o limitados, mas a resposta n\xc3\xa3o \xc3\xa9 garantida de sempre ser correta. Via uma aplica\xc3\xa7\xc3\xa3o da Desigualdade de\xc2\xa0Markov, um algoritmo Las Vegas pode ser convertido em um algoritmo Monte Carlo via rescis\xc3\xa3o antecipada.'