¿Cuáles son algunos ejemplos de funciones que son más rápidas de verificar que de calcular?

Question

Soy consciente de que Algoritmo de Freivalds para verificar la multiplicación de matrices.
¿Hay más funciones como ésta?
(También las verificaciones probabilísticas)

Answer 1

Un ejemplo sería la función $R$ mapeando un polinomio $p \in \mathbb Q[X]$ a su conjunto de raíces racionales (en el conjunto de potencias $\mathcal P(\mathbb Q)$ ).

Answer 2

Sin contar los algoritmos teóricos eficientes, la resolución de un sistema lineal denso es $O(N^3)$ mientras que la verificación es $O(N^2)$ .

La factorización de enteros es difícil. La verificación es inmediata.

Encontrar tres cubos enteros que sumen $42$ requirió más de un millón de horas de cálculo (y, según tengo entendido, sólo se realizó una vez en la historia de la computación). La verificación se hace en un microsegundo.

Answer 3

Un ejemplo relativamente famoso de esto se encuentra en Lander, L. J., & Parkin, T. R. (1966) una prueba de 2 frases, que resuelve una conjetura que ni siquiera Euler pudo resolver. El problema consiste en encontrar cuatro quintas potencias que sumen otra quinta potencia. Fácil de comprobar pero difícil de encontrar. Se pueden encontrar ejemplos similares con otras ecuaciones diofantinas complicadas.

Para reformular esto en un problema sobre funciones, se podría preguntar sobre los ceros de $f(v,w,x,y,z)=v^5+w^5+x^5+y^5-z^5$ .