Uno de los principales problemas sin resolver en teoría de la computabilidad está relacionado con este problema; si P=NP, entonces sería al menos posible que se puedan hallar algoritmos así, y seguramente se buscarían con más ahínco que hoy en día.