Tomemos como ejemplo la reducción 3d → 2d: ¿Cuál es el costo de simular un autómata celular 3d con un autómata celular 2d?
Aquí hay un montón de preguntas más específicas:
¿Qué tipo de algoritmos cambiarán su complejidad de tiempo, en cuánto?
¿Cuál sería la idea básica para la codificación? ¿Cómo se asigna una cuadrícula 3D de manera eficiente (o no eficiente ...) a una cuadrícula 2D? (El desafío parece lograr la comunicación entre dos celdas que originalmente eran vecinas en la cuadrícula 3d, pero ya no son vecinas en la cuadrícula 2d).
En particular, estoy interesado en la deriva de la complejidad para los algoritmos de complejidad exponencial (que supongo que sigue siendo exponencial sea cual sea la dimensión, ¿es el caso?)
Nota: No me interesan las clases de baja complejidad para las cuales el método de E / S elegido influye en las complejidades. (Quizás lo mejor es asumir que el método de E / S no tiene dimensiones: se realiza localmente en una celda específica durante una cantidad variable de pasos de tiempo).
Algún contexto: estoy interesado en la reescritura de gráficos locales paralelos, pero esos gráficos están más cerca de las cuadrículas 3D (o tal vez ωd ...) que de las cuadrículas 2d, me gustaría saber qué esperar de una implementación de hardware en un 2-dimentional chip de silicio.
fuente