No sabemos si los problemas cuya solución es fácil de verificar son también fáciles de resolver
Existen problemas cuya solución, una vez propuesta, es fácil de comprobar. Dado un sudoku resuelto, verificar que es correcto lleva un momento. Dada una ruta que visita todas las ciudades por debajo…
Si se pide a un grupo de personas que escriba una secuencia de cien caras y cruces imaginando lanzamientos de moneda, y a otro grupo que lance realmente la moneda, un observador entrenado distingue…
Considérese una enfermedad que afecta a una de cada diez mil personas y una prueba que detecta correctamente al noventa y nueve por ciento de los enfermos y da un uno por ciento de falsos positivos…
Supongamos un algoritmo que comprima cualquier archivo reduciendo su tamaño al menos en un bit, y que permita recuperar el original sin pérdida.