Nieskończenie duże, ale lokalnie skończone problemy obliczeniowe

To pytanie jest inspirowane komentarzem Jukki Suomeli do innego pytania .

Jakie są przykłady nieskończenie dużych, ale lokalnie skończonych problemów obliczeniowych (i algorytmów)?

Innymi słowy, jakie są przykłady obliczeń, które zatrzymują się w skończonym czasie, w których każda Maszyna Turinga odczytuje i przetwarza tylko dane skończone, ale w sumie obliczenia rozwiązują problem nieskończonej wielkości, jeśli istnieje nieskończenie wiele maszyn Turinga połączonych w sieć?

Oto tylko jeden przykład: rozproszony algorytm, który znajduje maksymalne upakowanie krawędzi na wykresie o ograniczonym stopniu.

Definicja problemu

Biorąc pod uwagę prosty nieukierunkowane wykres , co stanowi uszczelnienie krawędzi (lub odpowiednio frakcyjną) kojarzy się na wadze w ( E ) z każdej krawędzi e ∈ E tak, że dla każdego węzła v ∈ V , całkowita waga krawędzi incydentu v wynosi co najwyżej 1 . Węzeł jest nasycony, jeśli całkowita waga krawędzi zdarzenia jest równa 1 . Wypełnienie krawędzi jest maksymalne, jeśli wszystkie krawędzie mają co najmniej jeden nasycony punkt końcowy (tzn. Żaden z obciążników nie może być zachłannie przedłużony).$G = (V,E)$$w(e)$$e \in E$$v \in V$$v$$1$$1$

Zauważ, że maksymalne dopasowanie określa maksymalne wypełnienie krawędzi (zestaw w ( e ) = 1 iff e ∈ M ); stąd łatwo go rozwiązać w klasycznym scentralizowanym otoczeniu (zakładając, że G jest skończone).$M \subseteq E$$w(e) = 1$$e \in M$$G$

Pakiety brzegowe faktycznie mają pewne zastosowania, przynajmniej jeśli zdefiniuje się aplikację w zwykłym sensie TCS: zbiór nasyconych węzłów tworzy przybliżenie minimalnej osłony wierzchołków (oczywiście ma to sens tylko w przypadku skończonego G ) .$2$$G$

Model obliczeń

Zakładamy, że istnieje stała globalna taka, że ​​stopień dowolnego v ∈ V wynosi co najwyżej Δ .$\Delta$$v \in V$$\Delta$

Aby zachować to jak najbliżej ducha pierwotnego pytania, zdefiniujmy model obliczeń w następujący sposób. Zakładamy, że każdy węzeł jest maszyną Turinga, a krawędź { u , v } ∈ E jest kanałem komunikacji między u i v . Taśma wejściowe V koduje stopień ° ( v ), z v . Dla każdego v ∈ V krawędzie padające na v są oznaczone (w dowolnej kolejności) liczbami całkowitymi 1 , 2 , $v \in V$$\{u,v\} \in E$$u$$v$$v$$\deg(v)$$v$$v \in V$$v$ ; są to tak zwanelokalne etykiety krawędzi(etykieta { u , v } ∈ E może być inna dla u i v ). Urządzenie posiada instrukcje, dzięki którym może wysyłać i odbierać wiadomości przez każdą z tych krawędzi; maszyna może zwracać się do swoich sąsiadów za pomocą lokalnych etykiet krawędzi.$1,2,\dotsc,\deg(v)$$\{u,v\} \in E$$u$$v$

Wymagamy, że maszyny obliczyć prawidłową krawędzi upakowania dla G . Dokładniej, każde v ∈ V musi wydrukować na swojej taśmie wyjściowej kodowanie w ( e ) dla każdej krawędzi e padającej na v , uporządkowane według lokalnych etykiet krawędzi, a następnie zatrzymać.$w$$G$$v \in V$$w(e)$$e$$v$

Mówimy, że rozproszony algorytm znajduje maksymalne upakowanie zbocza w czasie T , jeśli poniższe odnosi się do dowolnego wykresu G o maksymalnym stopniu Δ i dla dowolnego lokalnego oznaczenia zbocza G : jeśli zastąpimy każdy węzeł G identyczną kopią maszynę Turinga A i uruchom maszyny, a następnie po krokach T wszystkie maszyny wydrukowały prawidłowe (globalnie spójne) rozwiązanie i zatrzymały się.$A$$T$$G$$\Delta$$G$$G$$A$$T$

Nieskończoności

Teraz wszystkie powyższe mają doskonały sens, nawet jeśli zbiór węzłów jest w nieskończoność nieskończony.$V$

Formułowanie problemu i model obliczeniowy nie mają żadnych odniesień do , bezpośrednio lub pośrednio. Długość wejścia dla każdej maszyny Turinga jest ograniczona stałą.$|V|$

Co jest znane

Problem można rozwiązać w skończonym czasie, nawet jeśli jest nieskończony.$G$

Problem nie jest trywialny, ponieważ wymaga pewnej komunikacji. Ponadto czas działania zależy od . Jednak dla dowolnego ustalonego Δ problem można rozwiązać w stałym czasie, niezależnie od wielkości G ; w szczególności problem można rozwiązać na nieskończenie dużych wykresach.$\Delta$$\Delta$$G$

Nie sprawdziłem, jaki jest najbardziej znany czas działania w zdefiniowanym powyżej modelu (który nie jest zwykłym modelem stosowanym w tej dziedzinie). Mimo to, czas trwania, który jest wielomian w powinno być dość łatwe do osiągnięcia, i myślę uruchomioną czas, jaki ma sublinear w hemibursztynianu jest niemożliwe.$\Delta$$\Delta$

Znalezienie nowej generacji automatu komórkowego .

Można to rozwiązać zgodnie z opisem w stałym czasie. $\;$ (tj. niezależnie od danych wejściowych)

Zasadniczo każdy problem, który jest co najmniej tak trudny jak kolorowanie, wymaga algorytmu o czasie działania zależnym od liczby węzłów w sieci, a zatem nie może działać na nieskończonym, ale lokalnie skończonym grafie. Wynika to z początkowego dziennika Linial * n dolnej granicy.

$AC^0$$AC^0$