Nehmen wir als Beispiel die 3D → 2d-Reduktion: Was kostet die Simulation eines 3D-Zellularautomaten durch einen 2D-Zellularautomaten?
Hier sind einige spezifischere Fragen:
Um wie viel wird sich die zeitliche Komplexität von Algorithmen ändern?
Was wäre die Grundidee für die Codierung; Wie wird ein 3D-Raster effizient (oder nicht effizient ...) einem 2D-Raster zugeordnet? (Die Herausforderung scheint darin zu bestehen, eine Kommunikation zwischen zwei Zellen zu erreichen, die ursprünglich Nachbarn im 3D-Raster waren, aber keine Nachbarn mehr im 2D-Raster sind.)
Insbesondere interessiert mich die Komplexitätsdrift für exponentielle Komplexitätsalgorithmen (die meiner Meinung nach unabhängig von der Dimension exponentiell bleibt, ist dies der Fall?)
Hinweis: Ich interessiere mich nicht für Klassen mit geringer Komplexität, für die die ausgewählte E / A-Methode einen Einfluss auf die Komplexität hat. (Vielleicht ist es am besten anzunehmen, dass die E / A-Methode dimensionslos ist: lokal in einer bestimmten Zelle während einer variablen Anzahl von Zeitschritten.)
Einige Zusammenhänge: Ich bin an einem parallelen Umschreiben lokaler Diagramme interessiert, aber diese Diagramme sind näher an 3D-Gittern (oder vielleicht ωd…) als an 2D-Gittern. Ich würde gerne wissen, was von einer Hardware-Implementierung auf einem 2-dimensionalen zu erwarten ist Siliziumchip.
quelle