Unendlich große, aber lokal begrenzte Rechenprobleme

Diese Frage wurde durch einen Kommentar von Jukka Suomela zu einer anderen Frage inspiriert .

Was sind Beispiele für unendlich große, aber lokal begrenzte Rechenprobleme (und Algorithmen)?

Mit anderen Worten, was sind Beispiele für Berechnungen, die in endlicher Zeit anhalten, in denen jede Turing-Maschine nur endliche Daten liest und verarbeitet, aber insgesamt löst die Berechnung ein Problem mit unendlicher Größe, wenn unendlich viele Turing-Maschinen miteinander vernetzt sind?

Nur um einige Ideen zu geben, was möglich ist (aber etwas nicht trivial), hier ein Beispiel: Ein verteilter Algorithmus, der a findet maximale Kantenpackung auf einem Graphen mit begrenztem Grad findet.

Problem Definition

Wenn ein einfacher ungerichteter Graph , ordnet eine Kantenpackung (oder eine fraktionelle Übereinstimmung) jeder Kante e ∈ E ein Gewicht w ( e ) zu, so dass für jeden Knoten v ∈ V das Gesamtgewicht der Kanten gilt, auf die einfällt v ist höchstens 1 . Ein Knoten ist gesättigt, wenn das Gesamtgewicht der einfallenden Kanten gleich 1 ist . Eine Randverpackung ist$G = (V,E)$$w(e)$$e \in E$$v \in V$$v$$1$$1$ Kantenpackung maximal, wenn alle Kanten mindestens einen gesättigten Endpunkt haben (dh keine der Gewichte kann gierig verlängert werden).

Man beachte, dass eine maximale Übereinstimmung eine maximale Kantenpackung definiert (setze w ( e ) = 1, wenn e ∈ M ist ); daher ist es einfach, in einer klassischen zentralisierten Umgebung zu lösen (vorausgesetzt, G ist endlich).$M \subseteq E$$w(e) = 1$$e \in M$$G$

Kantenpackungen haben tatsächlich einige Anwendungen, zumindest wenn man eine Anwendung im üblichen TCS-Sinne definiert: Die Menge der gesättigten Knoten bildet eine Approximation einer minimalen Scheitelbedeckung (natürlich macht dies nur im Fall eines endlichen G Sinn ). .$2$$G$

Modell der Berechnung

Wir nehmen an, dass es eine globale Konstante so dass der Grad von v ∈ V höchstens Δ beträgt .$\Delta$$v \in V$$\Delta$

Um dies so nah wie möglich an der ursprünglichen Frage zu halten, definieren wir das Berechnungsmodell wie folgt. Wir nehmen an, dass jeder Knoten eine Turing-Maschine ist und eine Kante { u , v } ∈ E ein Kommunikationskanal zwischen u und v ist . Das Eingabeband von v codiert den Grad deg ( v ) von v . Für jedes v ∈ V werden die auf v einfallenden Kanten (in beliebiger Reihenfolge) mit ganzen Zahlen 1 , 2 , $v \in V$$\{u,v\} \in E$$u$$v$$v$$\deg(v)$$v$$v \in V$$v$ ; Diese werden alslokale Kantenbeschriftungen bezeichnet(die Beschriftung von { u , v } ∈ E kann für u und v unterschiedlich sein ). Das Gerät verfügt über Anweisungen, mit denen es Nachrichten über jede dieser Kanten senden und empfangen kann. Eine Maschine kann ihre Nachbarn über die lokalen Kantenbeschriftungen ansprechen.$1,2,\dotsc,\deg(v)$$\{u,v\} \in E$$u$$v$

Wir fordern, dass die Maschinen eine gültige Kantenpackung für G berechnen . Genauer gesagt, jedes v ∈ V weist auf seiner Ausgabeband eine Codierung von zu druck w ( e ) für jede Kante e Vorfall v , die von den lokalen Kanten Etiketten geordnet und dann zu stoppen.$w$$G$$v \in V$$w(e)$$e$$v$

Wir sagen, dass ein verteilter Algorithmus eine maximale Kantenpackung in der Zeit T findet , wenn für einen Graphen G mit maximalem Grad Δ und für eine lokale Kantenbeschriftung von G gilt : Wenn wir jeden Knoten von G durch eine identische Kopie von ersetzen Die Turing-Maschine A und die Maschinen starten, dann nach T Schritten haben alle Maschinen eine gültige (global konsistente) Lösung gedruckt und angehalten.$A$$T$$G$$\Delta$$G$$G$$A$$T$

Unendlichkeiten

Nun ergibt all das Sinn, auch wenn die Menge der Knoten unendlich ist.$V$

Die Problemformulierung und das Berechnungsmodell enthalten keine Verweise auf , direkt oder indirekt. Die Länge der Eingabe für jede Turingmaschine ist durch eine Konstante begrenzt.$|V|$

Was bekannt ist

Das Problem kann in endlicher Zeit gelöst werden, auch wenn unendlich ist.$G$

Das Problem ist in dem Sinne nicht trivial, dass eine gewisse Kommunikation erforderlich ist. Darüber hinaus hängt die Laufzeit von . Für jedes feste Δ kann das Problem jedoch unabhängig von der Größe von G in konstanter Zeit gelöst werden ; Insbesondere ist das Problem bei unendlich großen Graphen lösbar.$\Delta$$\Delta$$G$

Ich habe nicht überprüft, welche Laufzeit in dem oben definierten Modell die bekannteste ist (was nicht das auf dem Gebiet übliche Modell ist). Trotzdem sollte eine Laufzeit, die in polynomisch ist, ziemlich einfach zu erreichen sein, und ich halte eine Laufzeit, die in Δ sublinear ist, für unmöglich.$\Delta$$\Delta$

Die nächste Generation eines Zellularautomaten finden .

Dies kann wie beschrieben in konstanter Zeit gelöst werden. $\;$ (dh unabhängig von der Eingabe)

Grundsätzlich erfordert jedes mindestens so schwierige Problem wie das Einfärben einen Algorithmus, dessen Laufzeit von der Anzahl der Knoten im Netzwerk abhängt und daher nicht in einem unendlichen, aber lokal endlichen Graphen funktioniert. Dies folgt aus Linials wegweisendem Protokoll * n Untergrenze.

Das passt nicht ganz zu Ihrer Definition, aber ich denke nur wegen der Uneinheitlichkeit. Vor dem Zeigen der Parität war nicht in$AC^0$, Sipser (ich glaube es war) hat gezeigt, dass jede unendliche Paritätsfunktion (eine Funktion für zählbar viele Variablen, die die Ausgabe ändert, wenn eine einzelne Eingabe geändert wird) nicht in "infinitary" gelöst werden kann $AC^0$. "