Wpływ wymiaru automatów komórkowych na klasy złożoności

Weźmy jako przykład redukcję 3d → 2d: Jaki jest koszt symulacji automatu komórkowego 3d przez automat komórkowy 2d?

Oto kilka bardziej szczegółowych pytań:

1. Jakiego rodzaju algorytmów zmieni się ich złożoność czasowa o ile?

2. Jaki byłby podstawowy pomysł na kodowanie; w jaki sposób siatka 3d jest wydajnie (lub nie wydajnie…) mapowana na siatkę 2D? (Wyzwaniem wydaje się osiągnięcie komunikacji między dwiema komórkami, które pierwotnie sąsiadują na siatce 3d, ale nie są już sąsiadami na siatce 2d).

3. W szczególności interesuje mnie dryf złożoności algorytmów złożoności wykładniczej (która, jak sądzę, pozostaje wykładnicza niezależnie od wymiaru, czy to prawda?)

Uwaga: Nie interesują mnie klasy o niskiej złożoności, dla których wybrana metoda wejścia / wyjścia ma wpływ na złożoność. (Być może najlepiej jest założyć, że metoda I / O jest bezwymiarowa: wykonywana lokalnie na jednej konkretnej komórce podczas różnych kroków czasowych).

Trochę kontekstu: jestem zainteresowany równoległym przepisywaniem grafów lokalnych, ale te wykresy są bliższe siatkom 3d (a może ωd…) niż siatkom 2d, chciałbym wiedzieć, czego się spodziewać po implementacji sprzętowej na 2-wymiarowym chip krzemowy.

Wyjaśnię fragmenty tego artykułu: Symulowanie automatów komórkowych 3D za pomocą automatów komórkowych 2D .

Zacznijmy od kodowania siatki, funkcji . Intuicyjnie nie zachowuje odległości, ponieważ liczba komórek w odległości mniejszej niż od początku nie będzie taka sama. Trzeba będzie zamieścić te informacje komórek w niektórych taką samą liczbę komórek, ale który będzie jakoś z formularza , ale wtedy trzeba mieć . Te i są trochę jak promień pojęcia sąsiedztwa, które można znaleźć w dowolnym automacie komórkowym.$t:\mathbb Z^3 → \mathbb Z^2$$t$$R$$R^3$$r^2$$r>R$$r$$R$

Tak więc transformacja artykułu sprawi, że rzeczy będą zasadniczo większe o siłę co najmniej . Że jeśli punkty są oddalone od na pierwszej siatce, będą one oddalone od co najmniej na drugiej siatce. Niestety dane osadzanie znajduje się tylko w .$3/2$$d$$O(\sqrt d^3)$$O(d^3)$

Jest to jednak bardzo ważna uwaga: nie uzyskuje się tego samego sąsiedztwa niż w pierwszym automacie i dlatego wcześniej powiedziałem „trochę jak”. Aby zacytować artykuł:

oczywiste jest, że będą komórki, które są bardzo blisko w i takie, że [ich kodowanie będzie] dowolnie daleko w$\mathbb Z^3$$\mathbb Z^2$

To także działa na czas: czas wykonania jednego kroku w może być dowolnie długi w . Zauważ, że kodowanie jest bardziej symulacją: 2D CA autor nawet symuluje obliczenie funkcji .$\mathbb Z^3$$\mathbb Z^2$$t:\mathbb Z^3 → \mathbb Z^2$

Można bezpiecznie powiedzieć, że złożoność (w czasie) dowolnego algorytmu uruchomionego na urzędzie certyfikacji 3D eksploduje po uruchomieniu na kodowaniu tego urzędu certyfikacji 3D w urzędzie 2D. Autor twierdzi, że nie może być związany żadną funkcją w swojej symulacji. I mówię, że eksplozja jest co najmniej wykładnicza w ogóle, ponieważ czas propagacji informacji zależy od pozycji.

Pomysł uruchamiania algorytmów na automatach komórkowych wydaje mi się już trochę dziwny, ale to sprawa osobista. To jednak nic w porównaniu z ideą implementacji automatu komórkowego w chipie krzemowym, czy to tylko ja?