A busca por maior poder computacional, sempre esteve presente na computação o que levou à criação de arquiteturas paralelas compostas por milhares de unidades de processamento, como ocorre nas arquiteturas das GPUs. Neste contexto, apresenta-se uma pesquisa para utilizar o poder computacional das GPUs, através da arquitetura CUDA, buscando resolver problemas computacionais, encontrados na classe NP-Completo, estes que podem levar anos para serem resolvidos. São apresentadas três estratégias de abordagem com suas limitações e benefícios. Com os resultados obtidos, há evidencias que a arquitetura é eficiente na solução destes problemas.