¿Hay un problema del Proyecto Euler que es un problema de NP?

[Supongo que te refieres a un problema computacionalmente “difícil”, como una instancia de la clase de problemas NP-completos .]

Se supone que los problemas del Proyecto Euler se pueden resolver en menos de un minuto de tiempo de cálculo si se aplica un algoritmo adecuado, por lo que en ese sentido no puede haber ningún problema insoluble. Sin embargo, hay algunos problemas combinatorios que son bastante difíciles y para los cuales solo se conocen algoritmos con comportamiento exponencial. No quiero enumerar ninguno (ya que esto puede considerarse como un spoiler), pero como pista hay algunos que requieren encontrar divisores de factoriales de tamaño mediano o productos de muchos (pero no demasiados) números primos con ciertas propiedades . Estos huelen mucho a instancias de problemas de mochila. He resuelto al menos dos de ellos donde la primera idea conduce a un algoritmo O (2 ^ N) que sería demasiado lento para la instancia dada, mientras que un pensamiento más duro reveló un algoritmo O (sqrt (2) ^ N), que puede resolver la instancia en un tiempo razonable. Por cierto, mi problema NP-completo favorito es el siguiente: dado un cubo lleno de piedras, divídalas en dos partes para que la diferencia de peso entre ambas partes sea mínima. Bastante simple, ¿no te parece? Y, sin embargo, tan difícil … Hay problemas del Proyecto Euler con exactamente esta estructura.

Related Content

Empleos y carreras: ¿Puedo conseguir un trabajo en un lugar como Google, Facebook, etc. con un título en matemáticas?

Cómo escribir un programa en C para verificar si para cualquier triplete entero (x, y, z) y otro entero n, [matemática] n ^ x + n ^ y = n ^ z [/ matemática] ocurre para (a, b) siendo la entrada donde [matemáticas] a \ leq n \ leq b [/ matemáticas]

¿Qué importancia tiene UPTU para la universidad de informática de MNN en Allahabad?

¿Qué es una explicación intuitiva de los teoremas de jerarquía y sus pruebas en la teoría de la complejidad computacional?

Si g (x) es una función unidireccional débil, ¿es f (x) = x (exclusivo o) g (x) una función unidireccional? Si es así, ¿puede ser fuerte?

Sí, hay problemas en el Proyecto Euler para los que no se conocen soluciones de tiempo polinómico (no voy a poner la identificación de ningún problema aquí, ya que puede considerarse como un spoiler) .

Se espera que algunos de estos problemas se resuelvan con una búsqueda completa ingenua, algunos requieren agregar algún tipo de poda o heurística para que su solución funcione lo suficientemente rápido. Por lo general, tales tareas tienen restricciones bastante pequeñas, como resultado, las soluciones exponenciales se ajustan bien a la regla de un minuto.

Aquí estoy asumiendo que está preguntando sobre problemas que no están en P 🙂 Como ha sido señalado por otras personas aquí, cualquier problema de P también es NP.

Samuel Schlesinger

Es casi seguro que no, aunque puede haber generalizaciones de algunos que sí lo son, ya que una sola instancia de un problema nunca se completa con NP. Dicho esto, si hubiera una instancia de un problema de NP completo en el Proyecto Euler, probablemente habría algún buen truco o estrategia que le permitiría calcularlo de manera más eficiente, ya que de lo contrario pedir un problema aleatorio de NP completo de cualquier razonable El tamaño es simplemente masoquismo.

Jesse Pollard

No se supone que sea.

“Los problemas son de diversa dificultad, pero cada uno se puede resolver en menos de un minuto utilizando un algoritmo eficiente en una computadora con modesta potencia”.

Proyecto Euler – Wikipedia

Samuel Schlesinger

More Interesting

¿Cuáles son los cursos matemáticos recomendados para el aprendizaje automático y el procesamiento de big data?

¿Cómo puedo ordenar rápidamente una matriz de elementos que ya está ordenada, excepto por un pequeño número de elementos, por ejemplo, hasta 1/4 del total, cuyas posiciones se conocen, por ejemplo, 1,2,3,4,8,6 , 7,8,2,10,11,3,13,14,15,16. Este conjunto se ordena guardar 4,8,11?

¿Es posible escribir un programa para tabular la cantidad de tiempo que llevaría ver todos los programas en la lista instantánea de Netflix?

Cómo resolver la recurrencia T (n) = T (n - 1) + n usando el teorema del maestro

¿Debo leer matemáticas y algoritmos discretos primero antes de comenzar la programación competitiva?

¿Qué debe incluirse en cualquier programa que use la función matemática?

Para los usuarios, ¿se está volviendo Facebook más valioso, útil y digno de más tiempo invertido o menos? ¿Por qué? ¿Hay alguna evidencia de Facebook de que la Ley de Metcalfe es cierta (para n usuarios, el valor de la red aumenta en nxn)?

¿Cuáles son los problemas finales más interesantes del cálculo?

¿Qué vale la pena aprender antes de ir a la carrera de ciencias de la computación para tener éxito allí?

¿Puedo aplicar a la escuela de posgrado para estudiar informática teórica?

¿La comunidad académica evita los intentos de resolver un problema NP-difícil en tiempo polinómico?

¿Es importante tener una excelente comprensión de la informática teórica para convertirse en un mejor programador?

¿Puedo convertirme en un buen científico de datos con programación pero no con habilidades matemáticas?

¿Qué aprendería una función de valor de acción de estado si colocamos múltiples objetivos en el espacio de estado y nos movemos de un punto de partida a un objetivo y luego de un objetivo a otro utilizando el aprendizaje de refuerzo con aproximación de funciones?

¿Por qué este bucle, usado para agregar caracteres adyacentes en un vector, produce una salida extraña?