¿Cuál es el problema más difícil que se puede resolver sin usar derivados de orden superior?

Las matemáticas pueden ser complicadas, y algunos problemas que parecen difíciles pueden ser realmente simples, y viceversa. Supongo que el OP sabe acerca de los sistemas de ecuaciones lineales (donde hay múltiples ecuaciones de la forma [matemáticas] a_1 \ cdot x_1 + \ ldots + a_n \ cdot x_n = b [/ matemáticas]). Tales sistemas generalmente se resuelven en el primer año de álgebra lineal en las universidades cuando los coeficientes y las variables son números reales. Un poco más desafiante es el caso en que ambos deben ser enteros, pero va esencialmente en la misma línea, con algunos trucos agregados porque no se puede dividir libremente.

Uno puede hacer que el problema sea aún más complejo al exigir que los coeficientes y las variables deben ser polinomios con coeficientes enteros y múltiples variables. Fue resuelto en 1930 por Szego y redescubierto 40 años después por Buchberger.

En lugar de pasar de enteros a polinomios, se puede observar la restricción a enteros positivos. Para los científicos informáticos es más difícil [doblemente exponencial en lugar de NP, escribir la solución, pero su existencia es la misma que la existencia de una solución con enteros arbitrarios.

Lo que quedaba por ver era la restricción de coeficientes y soluciones a polinomios con coeficientes enteros positivos. Este es un problema puro de “informática”, ya que no creo que los matemáticos estén muy interesados ​​en él, mientras que es la base para definir operaciones en conjuntos de elementos. Ese problema no se resolvió durante muchos años, hasta que se descubrió que no existe un algoritmo que pueda calcular una solución a este problema. La belleza del artículo de Narendran (Resolviendo ecuaciones lineales sobre semirremolques polinómicos, presentado en LICS 1996) es que el núcleo del resultado se basa en los hechos que:

  • un polinomio con coeficientes enteros positivos es monotónicamente creciente o constante;
  • entonces, si tiene el doble del mismo valor, su derivada debe ser 0;
  • entonces en ese caso el polinomio es una constante.

A partir de esto, Narendran codifica la multiplicación de enteros y, por lo tanto, las ecuaciones generales de diofantina (décimo problema de Hilbert). Animo a cualquiera a leer el periódico, al menos las primeras cuatro páginas: ¡las matemáticas elementales a veces pueden conducir a resultados profundos!