Aproximação e Complexidade de problemas de Procura local
Authors
Abstract
Este trabalho é apenas uma exposição sobre como abordar o tema da complexidade computacional no caso específico de problemas NP-difíceis quando são utilizados métodos heurísticos para a sua aproximação. Não é, nem pretende ser, uma compilação exaustiva de todos os resultados neste campo, mas antes uma contribuição para a divulgação desta área de trabalho. Para além disso, tenta servir todos aqueles que pretendam uma familiarização rápida com as principais definições e resultados mais importantes destas classificações de complexidade.Começando com uma secção condensada de resultados de "aproximabilidade", apresenta-se em seguida uma descrição da teoria da complexidade de problemas de Procura Local.