Influence de la dimension des automates cellulaires sur les classes de complexité

Prenons comme exemple la réduction 3d → 2d: Quel est le coût de simulation d'un automate cellulaire 3d par un automate cellulaire 2d?

Voici un tas de questions plus spécifiques:

1. Quels types d'algorithmes verront leur complexité temporelle modifiée, de combien?

2. Quelle serait l'idée de base pour l'encodage; comment une grille 3D est-elle efficacement (ou pas efficacement…) mise en correspondance avec une grille 2D? (Le défi semble atteindre la communication entre deux cellules qui étaient à l'origine voisines sur la grille 3D, mais ne sont plus voisines sur la grille 2D).

3. En particulier, je m'intéresse à la dérive de la complexité des algorithmes de complexité exponentielle (qui je suppose reste exponentielle quelle que soit la dimension, est-ce le cas?)

Remarque: je ne suis pas intéressé par les classes de faible complexité pour lesquelles la méthode d'E / S choisie a une influence sur les complexités. (Peut-être que le mieux est de supposer que la méthode d'E / S est sans dimension: effectuée localement sur une cellule spécifique pendant un nombre variable de pas de temps.)

Un peu de contexte: je suis intéressé par la réécriture de graphes locaux parallèles, mais ces graphes sont plus proches des grilles 3d (ou peut-être ωd…) que des grilles 2D, j'aimerais savoir à quoi s'attendre d'une implémentation matérielle sur une 2 dimensions puce de silicium.

J'expliquerai des morceaux de cet article: Simuler des automates cellulaires 3D avec des automates cellulaires 2D .

Commençons par l'encodage de la grille, une fonction . Intuitivement, ne peut pas conserver la distance car le nombre de cellules à une distance inférieure à de l'origine ne sera pas le même. Vous devez intégrer ces propos de R 3 cellules dans une même nombre de cellules , mais qui sera en quelque sorte de la forme r 2 , mais alors vous devez avoir r > R . Ces r et R sont un peu comme le rayon de la notion de voisinage que l' on trouve dans n'importe quel automate cellulaire.$t:\mathbb Z^3 → \mathbb Z^2$$t$$R$$R^3$$r^2$$r>R$$r$$R$

$3/2$$d$$O(\sqrt d^3)$$O(d^3)$

Cependant, et c'est une remarque très importante, vous n'obtenez pas le même voisinage que dans le premier automate et c'est pourquoi j'ai déjà dit "un peu comme". Pour citer l'article:

$\mathbb Z^3$$\mathbb Z^2$

$\mathbb Z^3$$\mathbb Z^2$$t:\mathbb Z^3 → \mathbb Z^2$

Il est fort à parier que la complexité (dans le temps) de tout algorithme exécuté sur une autorité de certification 3D explosera lors de l'exécution sur l'encodage de cette autorité de certification 3D en une autorité de certification 2D. L'auteur dit qu'il ne peut être lié à aucune fonction dans sa simulation. Et je dis que l'explosion est au moins exponentielle en général, car le temps de propagation de l'information dépend de la position.

L'idée d'exécuter des algorithmes sur des automates cellulaires me semble déjà un peu bizarre, mais c'est personnel. Mais ce n'est rien comparé à l'idée d'une implémentation d'un automate cellulaire dans une puce de silicium, ou est-ce juste moi?