Existe um fenômeno empírico em computação de mudança de fase, o qual está associado a problemas NP-completos. Há uma conjectura, feita por Cheeseman em 1991, de que todo problema NP-completo está associado a este tipo de mudança de fase que, embora não haja até hoje uma demonstração matemática da validade desta conjectura, foi verificada em diversas classes de problemas NP-completos. Neste trabalho iremos descrever o fenômeno empírico da mudança de fase, seu aparecimento em diversos contextos e a forma como a robustez deste fenômeno tem guiado pesquisas na área de algoritmos para problemas NP-completos.