Considere o problema descritoAqui (reproduzido abaixo). Algum problema NP-completo mais conhecido pode ser reduzido a ele?

O problema:

Há uma fileira de casas. Cada casa pode ser pintada com três cores: vermelho, azul e verde. O custo de pintar cada casa com uma determinada cor é diferente. Você tem que pintar todas as casas de modo que não haja duas casas adjacentes com a mesma cor. Você tem que pintar as casas com um custo mínimo. Como você faria?

Nota: O custo da pintura da casa 1 vermelha é diferente do da pintura da casa 2 vermelha. Cada combinação de casa e cor tem seu próprio custo.