Considere la siguiente tarea algorítmica:
Entrada: un entero positivo , junto con su factorización prima
Encontrar: enteros positivos que minimizan , sujeto a la restricción de quex , y , z
x y z = n
¿Cuál es la complejidad de este problema? ¿Existe un algoritmo de tiempo polinómico? ¿Es NP-duro?
Este problema básicamente pregunta: de todos los sólidos rectangulares cuyo volumen es cuyas dimensiones son todos enteros, ¿cuál tiene la menor área de superficie?
Este problema fue planteado por Dan Meyer, bajo el título El problema matemático que 1,000 maestros de matemáticas no pudieron resolver . Hasta ahora, ninguno de los profesores de matemáticas con los que trabajó ha encontrado un algoritmo razonable para este problema. En su contexto, la definición de "razonable" es un poco imprecisa, pero como informáticos podemos hacer una pregunta más precisa sobre la complejidad de este problema.
El enfoque obvio es enumerar todas las posibilidades para , pero eso lleva tiempo exponencial. Los comentaristas en el blog de Dan Meyer han propuesto muchos algoritmos de candidatos eficientes que desafortunadamente todos resultaron ser incorrectos. Martin Strauss sugiere que este problema parece recordar vagamente a las 3 particiones , pero no puedo ver una reducción.
Permítanme aclarar algunas ideas falsas que he visto en los comentarios / respuestas:
No se puede reducir de 3 particiones simplemente reemplazando cada número con su potencia , ya que las funciones objetivas de los dos problemas son diferentes. La reducción obvia simplemente no funciona.2 q
No es cierto que la solución óptima implica elegir uno de para que sea el divisor más cercano de a . Veo a varias personas que suponen que este es el caso, pero de hecho, eso no es correcto. Esto ya ha sido refutado en la publicación del blog de Dan Meyer. Por ejemplo, considere ; , y 4 divide 68, por lo que podría pensar que al menos uno de debería ser 4; Sin embargo, eso no es correcto. La solución óptima es , , . Otro contraejemplo es , , pero la solución óptima esn 3 √ n=683 √x,y,zx=2y=2z=17n=2223 √x=37 , , . ( Puede ser cierto que para todo , la solución óptima implica hacer que al menos uno de sea igual al divisor más pequeño de más grande que o al divisor más grande de más pequeño que - No tengo un contraejemplo en este momento, pero si crees que esta afirmación es verdadera, necesitaría pruebas. No puedes asumir que es verdadera).z = 2x , y , z n 3 √ 3 √
"Hacer que sean del mismo tamaño" no parece dar necesariamente la respuesta óptima en todos los casos; vea la publicación de blog de Dan Meyer para contraejemplos. O, al menos, para algunas interpretaciones razonables de la frase "hacerlos más o menos del mismo tamaño", hay contraejemplos que muestran que esta estrategia no es óptima. Si desea probar alguna estrategia de ese tipo, asegúrese de exponer el reclamo con precisión y luego proporcionar una prueba matemática cuidadosa.
Un tiempo de ejecución de no es polinomial. Para que este problema esté en P, el tiempo de ejecución debe ser un polinomio en la longitud de la entrada . La longitud de la entrada es algo así como , no . El algoritmo de fuerza bruta obvio puede ejecutarse en tiempo u , pero eso es exponencial en y, por lo tanto, cuenta como un algoritmo de tiempo exponencial. Por lo tanto, eso no es útil.lg n n O ( n 3 ) O ( n 2 ) lg n
Respuestas:
Aquí hay una versión modificada del algoritmo "elegir divisor cerca de la raíz del cubo". Todavía debe ser la fuerza bruta en muchos casos, por lo que no estoy seguro de cuánto de una mejora real es prudente en cuanto a la enumeración de todos los casos. Sin embargo, lo envié como una corrección al algoritmo en OEIS (lo que generó resultados incorrectos) porque creo que debería ser exacto al menos.
Aquí está el algoritmo para encontrar (s1, s2, s3) y el área de superficie de un prisma rectangular dado su volumen n:
Este algoritmo enumera algunos de los triples (s1, s2, s3) pero solo necesita probar los divisores debajo de la raíz cúbica. (Dado que no los tres divisores pueden estar por encima de la raíz cúbica). De manera similar, s2 solo necesita probar divisores de n / s1 debajo de la raíz cuadrada de n / s1, ya que no ambos divisores pueden estar por encima de la raíz cuadrada)
Una nota sobre el paso 3: si la raíz cúbica es un divisor, entonces n es un cubo y podemos detenernos allí con un área de superficie mínima 6 * s1 ^ 2 desde el cuadro (s1, s1, s1).
Pitón:
fuente
El problema, por supuesto, estaría relacionado con la complejidad de factorización si no se proporcionaran descomposiciones principales. Dados los factores, y tomando registros de todos los factores primos, este problema parece ser casi lo mismo que minimizar la desviación de la media de las sumas de partición (ejercicio, tal vez analítico o experimentalmente, encuentre cuán estrechamente esta aproximación intuitiva de la problema se cumple).k
Aquí este es el caso de 3 vías (las sumas de partición son ). El caso de 2 vías ha sido ampliamente estudiado y es NP duro (desde la 1ª referencia). (Este caso de 2 vías no es exactamente lo mismo que el conocido problema de partición de 2 vías de NP completo donde las sumas de partición son iguales. Tenga en cuenta que las sumas de partición iguales implican 0 desviación en las sumas de partición y viceversa ) . La segunda referencia estudia 3- partición en modo y camino , en parte empíricamente, donde no hay tanto estudio como el caso de 2 vías.nlog(x),log(y),log(z) n
El problema difícil más fácil: Particionamiento de números / Mertens
Particionamiento de números multidireccional / Korf
fuente
Editar
Aquí hay un argumento informal de por qué es poco probable que exista un algoritmo rápido. Esa oración no ha cambiado, pero eliminé lo que solía estar aquí porque estaba estructurada de manera muy similar a la prueba formal en la siguiente sección y la discusión se estaba desviando de sus errores, algunos de los cuales noté a mí mismo y a uno de los cuales DW me señaló amablemente. Permítanme en cambio tratar de expresar la intuición detrás de esto.
¿Qué sucede cuando traducimos los mismos pasos en un álgebra diferente, como sumar y restar en lugar de multiplicar y dividir? Sabemos (véase el lema a continuación) que nuestro algoritmo encontrará una partición de 3 cuyos productos son iguales, si existe, o determinará que no existe tal partición de 3. Entonces, si pudiéramos traducir las mismas técnicas al grupo aditivo, podríamos encontrar una partición de 3 cuyas sumas son iguales, o determinar que no existe tal partición. En otras palabras, podríamos resolver 3 particiones en tiempo polinómico. Eso no es muy plausible.
Entonces, ¿por qué un algoritmo de este tipo funciona para la multiplicación y falla para la suma? Una posible razón es que cada número entero tiene una factorización prima única bajo multiplicación, pero es cíclico bajo suma. Otra es que la multiplicación forma un anillo con la suma, por lo que tiene otro conjunto de operaciones que puede usar. Otra es que tendrías que generalizar el algoritmo para que funcione para los no primos, y podría depender de su primalidad. Lo que DW señaló es que el método específico de traducción podría aumentar exponencialmente el tamaño de sus entradas. Y tal vez P = NP después de todo.
Pero si esas son las lagunas que permiten que funcione un algoritmo rápido, creo que aún es útil saberlo, porque sugiere dónde debemos enfocar nuestros esfuerzos. Deberíamos estar buscando algo que se rompa si intentamos aplicarlo a un problema de NP completo. Un enfoque que se generalizaría a otras álgebras probablemente sea ladrar al árbol equivocado. Sin embargo, sospecho que la multiplicación no es lo suficientemente diferente para que eso funcione, pero eso es solo una corazonada.
Lema
Mi motivación inmediata para demostrar esto fue completar una onda manual en mi prueba anterior de que, si existe una solución de cubo perfecto, es óptima. Sin embargo, esta fórmula podría ser útil para podar el árbol de búsqueda.
Pensamientos variados
No veo ninguna simetría obvia, excepto la intercambiabilidad de x, y y z, que solo nos da en el mejor de los casos un factor constante de 6. Tenemos algunas aceleraciones para la partición 2 que básicamente dicen que queremos que ambos términos estar tan cerca el uno del otro como sea posible, pero no veo de inmediato una aplicación para este problema.
Fuera de mi cabeza, simplemente tomar el registro de todos los números reduce inmediatamente esto a un problema clásico de 3 particiones usando la suma, o de manera equivalente, tomar algún número a la potencia de los números en cualquier problema de suma de 3 particiones lo convierte en un problema de multiplicación como este Eso implica que este problema no debería ser más fácil. Tenemos aquí la factorización prima, mientras que esa factorización no sería prima, pero ¿eso nos ayuda?
Gráficamente, la superficie xyz = 0 se vería como la unión de los planos xy, yz y xz, y para cualquier n positivo, la ecuación se vería como y = n / xz, por lo que cada corte a lo largo de un plano de coordenadas sería una hipérbola Generalmente podemos decir que la cantidad que estamos tratando de minimizar es más baja en el origen y crece más rápidamente a lo largo de la línea donde x = y = z. Si solo podemos buscar a lo largo de esta variedad, podríamos reducirnos a un problema bidimensional.
fuente