Por lo que podemos concluir que dado los certificados apropiados, es posible verificar rápidamente las respuestas afirmativas de nuestro problema (en tiempo polinomial) y es ésta la razón por la que el problema se encuentra en NP.