Un problema NP-completo trivial e ideado, se puede formular como: Dada una descripción de una máquina de Turing M que se detiene en tiempo polinómico, ¿existe una entrada de tamaño polinómico que M acepte? Es NP porque, dada una entrada, es simple comprobar si M acepta o no la entrada simulando M, es NP-duros porque el verificador para cualquier caso particular de un problema en NP puede ser codificado como una máquina M de tiempo polinomial que toma la solución para ser verificada como entrada.