Usando aleatoriedade para lidar com problemas computacionalmente difíceis em grafos

Muitos problemas relevantes em computação são computacionalmente difíceis — não se conhecem algoritmos polinomiais para resolvê-los —, o que motiva a busca por abordagens alternativas, como algoritmos para subclasses específicas, soluções aproximadas, paralelização e, particularmente, o uso de aleatoriedade. Este trabalho apresenta uma revisão bibliográfica sobre a aplicação de aleatoriedade em problemas difíceis em grafos, abordando duas formas principais: algoritmos aleatorizados e análise probabilística de algoritmos. Na primeira, considera-se algoritmos que têm acesso a bits aleatórios, permitindo o desenvolvimento de soluções mais simples, embora a aleatoriedade provavelmente não aumente o poder computacional. Na segunda, substituímos, de forma justificada, a análise de pior caso pela análise de caso médio ou pela análise suavizada, possibilitando resultados positivos para problemas complexos sob essa perspectiva.