São problemas da classe NP que são tão difíceis quanto qualquer outro problema NP.