¿Es posible resolver un problema de complejidad O (n!) Dentro de un tiempo razonable dado un número infinito de unidades de procesamiento y espacio infinito?Los límites del paralelismo (pregunta de entrevista de trabajo)
El ejemplo típico de O (n!) Problema es la búsqueda de fuerza bruta: probando todas las permutaciones (combinaciones ordenadas).
Seguro. Considere el Problema del Viajero Viajero en su estricta forma NP: dada esta lista de costos para viajar de cada punto a cada otro punto, ¿puede organizar un recorrido con un costo menor que K? Con la nueva CPU de núcleo infinito de Intel, usted simplemente asigna un núcleo a cada permutación posible, suma los costos (esto es rápido) y ve si algún núcleo funciona como un éxito.
Más generalmente, un problema en NP es un problema de decisión tal que una solución potencial puede verificarse en tiempo polinomial (es decir, eficientemente) y así (dado que las posibles soluciones son enumerables) cualquier problema puede resolverse eficientemente con suficientes CPUs
Claro, puede enumerar todas las soluciones posibles, pero ¿cómo proporcionar a cada unidad de procesamiento los datos requeridos? Tienes que distribuir datos y significa que tienes que comparar cada permutación entre sí. – psihodelia
No, no tiene que comparar todo para todo. Supongamos que quiere la solución de menor costo para un TSP. Calcule todos los costos en paralelo. Entonces, las CPU pares incluso comparan sus valores con los impares correspondientes y mantienen el resultado más económico. Haga ese tipo de comparación, y puede obtener la respuesta en el tiempo necesario para iniciar sesión. comparaciones O (n^n)> = O (n!), Y log (n^n) es n log n, por lo que el postprocesamiento sería en el peor O (n log n), que es polinomial. Sería posible hacer al menos tan bien en la configuración. –
Echemos un vistazo a TSP, que es: dado un gráfico ponderado completo encontrar un ciclo de Hamilton con el menor peso. Debe tener un procedimiento determinista para producir un ciclo hamiltoniano único en cada CPU. Debe asignar cada ciclo posible a cada CPU. Incluso si se puede calcular la longitud de un ciclo en un hilo de procesamiento completamente independiente, ¡hay n! ciclos. La pregunta es: ¿se pueden asignar todos los ciclos a las CPU de forma independiente? ¿No porque? Debido a la naturaleza determinista del ajuste de cuentas. – psihodelia
Sin tener en cuenta el costo de configuración (cualquiera que sea ... asignando un rango de valores a una unidad de procesamiento, por ejemplo), entonces sí. En tal caso, cualquier valor menor que infinito podría resolverse en una iteración simultánea en un número igual de unidades de procesamiento.
La configuración, sin embargo, es algo importante de ignorar.
¿Por qué cualquier valor menor que el infinito? Dado un número infinito de procesadores, ¿no deberían poder manejar un número igual (infinito) de procesos? Infinity me duele el cerebro a veces – Bob
@Bob: Porque cada valor es menor que infinito;) –
No, porque lleva un tiempo infinito distribuir un trabajo a máquinas infinitas; también lleva mucho tiempo abrir los cuadros e instalarlos. –
Parece que lo que realmente está preguntando es si un problema de O (n!) Complejidad puede reducirse a O (n^a) en una máquina no determinista; en otras palabras, si Not-P = NP. La respuesta a esa pregunta es no, hay algunos problemas Not-P que no son NP. Por ejemplo, un problema limitado de detención (que pregunta si un programa se detiene en la mayoría de los n pasos).
Tomé la respuesta si hay algunos problemas que pueden resolverse fácilmente. Está respondiendo por todos los problemas, que es igualmente legítimo y lo que la mayoría de las personas que respondieron no abordaron. –
Eso es verdad. Creo que nuestras respuestas son complementarias: hay algunos problemas que se reducen y otros que no. Ambos hechos son importantes. – tloflin
El problema sería distribuir el trabajo y recoger los resultados.
Si todas las CPU pueden leer la misma pieza de memoria a la vez, y si cada una tiene una ID de CPU única que conoce, entonces la ID se puede usar para seleccionar una permutación y el problema de distribución es Solucionable en tiempo constante.
Sin embargo, recopilar los resultados sería complicado. Cada CPU podría comparar con su vecino (numérico), y luego ese resultado en comparación con el resultado de los dos vecinos más cercanos, etc. Este será un proceso O (log (n!)). No estoy seguro, pero sospecho que O (log (n!)) Es hiperpolinomial, así que no creo que sea una solución.
O (log (n!)) = O (n log n). Eso es polinomio seguro. – Daniel
Si el problema es verificar las permutaciones/respuestas a un problema de complejidad O (n!), Entonces por supuesto puede hacerlo de manera eficiente con un número infinito de procesadores.
La razón es que puede distribuir fácilmente piezas atómicas del problema (una pieza atómica del problema podría, por ejemplo, ser una de las permutaciones para comprobar) con eficacia logarítmica.
Como un ejemplo simple, podría configurar los procesadores como un 'árbol binario', por así decirlo. Podrías estar en la raíz y hacer que los procesadores entreguen las permutaciones del problema (o lo que sea que sean las piezas más pequeñas del problema) a los procesadores de hojas para que las resuelvan, y terminarías resolviendo el problema en el registro (n!) hora.
Recuerde que es la entrega de las permutaciones a los procesadores que lleva mucho tiempo. Cada parte del problema se resolverá instantáneamente.
Editar: Se ha corregido mi publicación de acuerdo con los comentarios a continuación.
Dado que la cantidad de CPU utilizadas en el problema es n! en lugar de n, la configuración del "árbol binario" está en el orden de registro (n!). –
Tienes razón. ¡Mi error! – Cam
log n! es bastante bueno. Es un polinomio (aunque definitivamente no sublineal). –
Cada problema podría ser resuelto por una CPU, pero ¿quién entregaría estos trabajos a todas las CPU infinitas? En general, esta tarea está centralizada, por lo que si tenemos infinitos trabajos para entregar a todas las CPU infinitas, podríamos tomar un tiempo infinito para hacerlo.
En realidad, para la mayoría de los problemas reales la distribución de trabajos es un proceso paralelo, por lo que para O (n!) La distribución de problemas es O (n log n). –
No, N! es incluso más alto que NP. Pensar que el paralelismo ilimitado podría resolver el problema de NP en tiempo polinomial, que generalmente se considera una complejidad de tiempo "razonable", N! el problema es aún mayor que el polinomio en dicha configuración.
* N! es incluso más alto que NP * - [cita requerida]. ¿Y es incluso relevante? Siempre que el resultado sea verificable en tiempo polinomial, estará en NP. – kennytm
Es razonable decir que O (n!) Es más alto que O (2^n), ya que se está comparando con like. Sin embargo, un problema de NP se define como uno que se puede resolver en tiempo polinomial en una máquina de Turing no determinista, o equivalentemente, con resultados que son verificables en tiempo polinomial. No dice nada sobre la complejidad del tiempo para encontrar una solución. Por lo tanto, simplemente no entiendo lo que puede significar en su declaración. –
@KennyTM: disculpe por abusar de la notación NP.De alguna manera percibí que los problemas NP tienen la forma de k^N, tal vez debido a la omnipotencia de su definición académica. Tienes razón, no debería haber usado NP en mi respuesta original y no hay citas para mi declaración. Sin embargo, si un problema es verificable en el tiempo polinomial, difiere de un problema a otro. Mi intención original era decir que hay algunos problemas con N! la complejidad no se puede verificar en tiempo polinomial incluso con paralelismo ilimitado. – Codism
Mencionaste la búsqueda como un problema "típico", pero ¿realmente te preguntaron específicamente sobre un problema de búsqueda? Si es así, entonces sí, la búsqueda es típicamente paralelizable, pero en lo que puedo decir O (n!) En principio no implica el grado de concurrencia disponible, ¿verdad? Podría tener un problema de O (n!) Completamente serial, lo que significa que las computadoras infinitas no ayudarán. Una vez tuve un problema inusual de O (n^4) que en realidad era completamente serial.
Por lo tanto, la concurrencia disponible es lo primero, y en mi humilde opinión debe obtener puntos para sacar a la luz la ley de Amdahl en una entrevista. La próxima trampa potencial es la comunicación entre los procesadores, y en general la naturaleza del algoritmo. Considere, por ejemplo, esta lista de clases de aplicación: http://view.eecs.berkeley.edu/wiki/Dwarf_Mine. FWIW el código O (n^4) que mencioné anteriormente cae en la categoría FSM.
Otra anécdota algo relacionada: escuché a un ingeniero de un fabricante de supercomputadoras afirmar que si el 10% del tiempo de CPU se gastaba en bibliotecas MPI, consideraban que la paralelización era un éxito rotundo (aunque eso podría haber sido limitado a los códigos en el dominio de la química computacional).
Esto es como preguntar si un número infinito de monos tecleando en una computadora a prueba de destrucción de mono con un procesador de textos puede llegar a todas las obras de Shakespeare; dado una cantidad infinita de tiempo. El realista diría que no, ya que las condiciones no son físicamente posibles. El idealista dirá que sí; en teoría, puede suceder. Dado que la Ingeniería de Software (Ingeniería de Software, no Informática) se centra en el sistema real que podemos ver y tocar, entonces la respuesta es no. Si dudas de mí, ¡ve a construirlo y demuéstrame que estoy equivocado! EN MI HUMILDE OPINIÓN.
A veces la respuesta correcta es "¿Cuántas veces aparece esto con tu código base?" pero en este caso, hay una respuesta real.
La respuesta correcta es no, porque no todos los problemas se pueden resolver con un procesamiento paralelo perfecto. Por ejemplo, un problema similar a un vendedor ambulante debe comprometerse con una ruta para considerar el segundo tramo del viaje.
Suponiendo que una matriz de ciudades totalmente conectada, si desea mostrar todas las posibles rutas no cíclicas para nuestro cansado vendedor, se encuentra con un problema O (n!), Que puede descomponerse en una O (n) * O ((n-1)!) Problema. El problema es que necesitas comprometerte con una ruta (en el lado O (n) de la ecuación) antes de que puedas considerar las rutas restantes (en el lado O ((n-1)!) De la ecuación).
Dado que algunos de los cálculos deben realizarse antes de otros cálculos, entonces no hay forma de dispersar los resultados perfectamente en un único pase de dispersión/recopilación. Eso significa que la solución estará esperando los resultados de los cálculos que deben realizarse antes de que se pueda iniciar el "próximo" paso. Esta es la clave, ya que la necesidad de soluciones parciales previas proporciona un "cuello de botella" en la capacidad de proceder con el cálculo.
Dado que hemos demostrado que podemos hacer que varias de estas CPU infinitamente rápidas, infinitamente numerosas, esperen (incluso si están esperando por sí mismas), sabemos que el tiempo de ejecución no puede ser O (1) y solo necesitamos para elegir una N grande para garantizar un tiempo de ejecución "inaceptable".
No. Distribuya las permutaciones entre las CPU, que es una operación de tiempo polinomial. Cada CPU luego calcula su costo de permutación, que también es polinomial, en realidad O (n). Luego viene la comparación jerárquica, que también es tiempo polinomial. –
No puede distribuir todas las permutaciones entre las CPU sin haber explorado el espacio de permutación. Si tomaras un enfoque de escopeta, podrías perderte permutaciones (y definitivamente habría mucha superposición) y la "fase de recombinación" pagaría el precio de tener que clasificar toneladas de duplicados, lo que aún tomaría por encima de O (1) haciéndolo aún sujeto a "tiempo irracional" al hacer que la solución sea lo suficientemente grande. –
Sí, si n!
mob
Quiero saber dónde estabas entrevistando. ¡Es increíble que tengan una computadora con infinitas CPU y memoria! –
@Jeff: Tee hee. – Pierreten