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

Ao lidarmos com problemas computacionalmente difíceis — aqueles para os quais não se conhecem algoritmos polinomiais —, estratégias convencionais incluem desenvolver algoritmos para subclasses específicas ou usar algoritmos de aproximação. No entanto, muitas vezes a dificuldade do problema surge de poucas instâncias patológicas, tornando a análise de pior caso pessimista demais. Uma abordagem promissora nesses casos é a introdução de aleatoriedade, analisando o comportamento médio do problema em entradas aleatórias, o que permite o desenvolvimento de algoritmos eficientes com tempo esperado polinomial ou alta probabilidade de sucesso. Este trabalho visa compreender e sistematizar essas abordagens em problemas relacionados a grafos, produzindo um material introdutório que mostre como a aleatoriedade pode transformar problemas intratáveis em versões mais otimistas e tratáveis.