Dejemos que $n$ , $k$ y $m_1, \dots, m_k$ sean enteros positivos. ¿Cuál es el algoritmo más eficiente para averiguar si hay positivo enteros $a_1, \dots, a_k$ tal que $n = \sum_{i=1}^k a_i m_i$ ?
Para que las cosas no sean triviales, piense en $k$ siendo de cientos, y de $n$ y el $m_i$ con cientos de dígitos decimales, cada uno. -- Claramente, si elimináramos el requisito de que el $a_i$ son positivos, el Teorema Chino del Resto nos diría la respuesta pero hacer requieren que sean positivos.
El problema puede considerarse como un problema de monedas. Hay $k$ monedas con denominaciones $m_1,\dots,m_k$ y quieres expresar una cantidad $n$ con estas monedas. Como se ha dicho, el problema es una cuestión de programación entera que es NP-completa cuando $k$ es parte de la entrada. Está en P (con dependencia exponencial de $k$ ) cuando $k$ se fija mediante un algoritmo de Lenstra.
El problema está estrechamente relacionado con el problema de la moneda de Frobenius/Sylvester: encontrar el mínimo $n$ para que todo entero mayor tenga una representación de este tipo. Véase aquí y aquí . Un algoritmo polinómico cuando $k$ está acotado fue logrado por Ravi Kannan. (La dependencia de $k$ es doblemente exponencial).
Estos dos problemas (encontrar una representación para el $n$ y encontrar el valor de $n$ por encima de la cual siempre existe una representación) representan los dos primeros niveles en la jerarquía de Presburger. Un importante problema abierto aquí es encontrar un algoritmo P para problemas de orden superior en la Jerarquía de Presburger.
Por supuesto, otra cuestión importante es cómo resolver estas cuestiones en la práctica. Supongo que otras personas pueden responder a eso mejor que yo. Un método que ciertamente me viene a la mente es considerar la relajación de la programación lineal (es decir, permitir que los racionales $a_i$ s) y luego aplicar algunos redondeos y mejoras "locales".
El rango propuesto por el OP donde $k$ - (el número de monedas) está en los cientos es interesante. No sé si los algoritmos actuales pueden arañar este valor.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
2 votos
MO está destinado a temas de nivel de posgrado y superior.
14 votos
No veo cómo esto no es a nivel de escuela de posgrado o superior, sin embargo el problema parece ser equivalente al problema de la suma de subconjuntos no limitados, cuya completitud NP se menciona en mathoverflow.net/a/144983/12705 .
3 votos
La pregunta me parece perfectamente legítima (y Emil Jerábek ha proporcionado una respuesta a la misma - tal vez quiera publicarla como una respuesta real en lugar de un comentario, ahora que la pregunta se ha reabierto).
2 votos
Andy, esta es una cuestión importante relacionada con los trabajos de Sylvester y Frobenius donde se ha descubierto mucho en las últimas décadas.