🔢 mathematics

Parametrized complexity of relations between multidimensional subshifts

Dit artikel onderzoekt de geparametriseerde complexiteit van fundamentele relaties tussen meerdimensionale subshifts, waarbij één subshift als parameter wordt vastgelegd, en onthult hoe dynamische eigenschappen zoals periodiciteit en minimaliteit de berekeningscomplexiteit beïnvloeden, wat leidt tot nieuwe inzichten in de asymmetrieën tussen deze problemen en de ontdekking van niet-triviale decidable gevallen voor meerdimensionale subshifts van eindig type.

Oorspronkelijke auteurs: Nicanor Carrasco-Vargas, Benjamin Hellouin de Menibus, Rémi Pallen

Gepubliceerd 2026-02-16

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Nicanor Carrasco-Vargas, Benjamin Hellouin de Menibus, Rémi Pallen

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

De Complexiteit van Patronen: Een Reis door de Wereld van Subshifts

Stel je voor dat je een gigantisch, oneindig tapijt hebt. Op dit tapijt zijn vierkante tegels geplaatst, elk met een bepaalde kleur. Je mag geen willekeurige kleuren naast elkaar leggen; er zijn strikte regels. Bijvoorbeeld: "Een rode tegel mag nooit direct naast een blauwe tegel liggen."

In de wiskunde noemen we zo'n oneindig tapijt met regels een subshift. Het is een manier om patronen te beschrijven die zich over een heel vlak (of in meerdere dimensies) uitstrekken.

De auteurs van dit artikel (Nicanor, Benjamin en Rémi) kijken naar een heel specifiek vraagstuk: Hoe moeilijk is het om te bepalen of twee van deze tapijten eigenlijk hetzelfde zijn, of dat het ene tapijt in het andere past?

Ze doen dit op een slimme manier. In plaats van twee willekeurige tapijten te vergelijken, kiezen ze er één uit dat ze als "standaard" of "referentie" gebruiken. Dit noemen ze de parameter. Vervolgens krijgen ze een tweede tapijt als "input" en moeten ze bepalen hoe de twee zich tot elkaar verhouden.

Hier zijn de belangrijkste vragen die ze onderzoeken, vertaald naar alledaagse taal:

1. De Vragen: Zijn ze hetzelfde? Past het erin?

Stel, je hebt een standaard-tapijt (de parameter $Y$ ). Je krijgt nu een nieuw tapijt ( $X$ ) en moet beslissen:

Gelijkheid ( $X = Y$ ): Zijn deze twee tapijten exact hetzelfde patroon?
Conjugatie ( $X \simeq Y$ ): Kunnen we het ene tapijt omvormen tot het andere door een slimme, continue herschikking? (Alsof je het tapijt uitrekt of samendrukt, maar de structuur behoudt).
Inclusie ( $X \subseteq Y$ ): Past elk mogelijk patroon van $X$ ook binnen de regels van $Y$ ? (Is $X$ een deel van $Y$ ?)
Embedding ( $X \hookrightarrow Y$ ): Kunnen we $X$ zo in $Y$ "plakken" dat het niet uit elkaar valt? (Is $X$ een stukje van $Y$ ?)

2. De Uitdaging: De "Computerspel"-Analogie

De auteurs kijken naar de computergewicht van deze vragen. Kunnen we dit probleem oplossen met een computer?

SFT (Subshifts of Finite Type): Dit zijn tapijten met een korte, eindige lijst van verboden patronen. (Bijvoorbeeld: "Geen rode naast blauw").
Effectieve Subshifts: Dit zijn tapijten met een oneindige lijst van regels, maar die door een computer (een Turing-machine) stap voor stap gegenereerd kunnen worden.

De grote verrassing in dit artikel is dat het antwoord op de vraag "Is dit oplosbaar?" enorm afhangt van welk tapijt je als standaard ( $Y$ ) kiest.

3. De Grote Ontdekkingen

A. Het "Onmogelijke" tapijt

Als je als standaard ( $Y$ ) een heel complex tapijt kiest (bijvoorbeeld een dat een computer simuleert), worden de vragen vaak onoplosbaar. Het is alsof je vraagt: "Past dit nieuwe patroon in dit tapijt dat een oneindig lang wiskundig raadsel bevat?" De computer kan het antwoord nooit vinden; het blijft hangen. Dit wordt de "moeras van onbeslisbaarheid" genoemd.

B. Het "Simpele" tapijt

Maar als je als standaard ( $Y$ ) een heel simpel tapijt kiest (bijvoorbeeld een tapijt dat maar uit één patroon bestaat, of een eindig aantal patronen), worden sommige vragen plotseling oplosbaar.

Verrassend: Soms is het makkelijker om te checken of een patroon in een standaard past, dan om te checken of het deel uitmaakt van die standaard. Het is alsof het makkelijker is om te zeggen "Deze auto past in deze garage" dan om te zeggen "Deze garage is een exacte kopie van die andere garage".

C. De "Minimale" Tapijten

De auteurs ontdekten een interessante link met minimaliteit. Een tapijt is "minimaal" als het geen kleinere, zelfstandige patronen bevat die erin verstop zitten.

Als je standaard-tapijt een "minimaal" type is, wordt het probleem vaak makkelijker op te lossen.
Maar hier is de twist: Soms is een tapijt "minimaal" voor een bepaalde eigenschap, maar niet voor een andere. Als je de definitie van "minimaal" een beetje verandert, kan een probleem dat makkelijk was, plotseling onmogelijk worden.

4. Waarom is dit belangrijk?

Stel je voor dat je een detective bent die moet bepalen of twee verdachten (tapijten) hetzelfde zijn.

Als je verdachte A een heel simpel, voorspelbaar persoon is, kun je snel zeggen: "Ja, dat is niet dezelfde als verdachte B."
Maar als verdachte A een genie is dat oneindig complexe plannen maakt, kan het jaren duren om te bewijzen of verdachte B daar een kopie van is.

De auteurs tonen aan dat de eigenschappen van de standaard (is hij eindig? is hij minimaal? bevat hij oneindige patronen?) bepalen of de detective het antwoord kan vinden of dat hij vastloopt in een oneindige loop.

Samenvatting in één zin

Dit artikel laat zien dat de moeilijkheid om te bepalen of twee complexe patronen op elkaar lijken, niet alleen afhangt van het patroon dat je onderzoekt, maar vooral van de eigenschappen van het referentiepunt dat je kiest: soms is het een simpel rekensommetje, en soms is het een taak die een computer nooit kan voltooien.

Het is een fascinerend kijkje in hoe wiskundige regels en computerwetenschap samenkomen om te bepalen wat we wel en niet kunnen weten over de oneindige patronen in onze wereld.

Titel: Parametriseerde complexiteit van relaties tussen multidimensionale subshifts

Auteurs: Nicanor Carrasco-Vargas, Benjamin Hellouin de Menibus, Rémi Pallen.

1. Probleemstelling en Context

Het artikel onderzoekt de parametriseerde complexiteit van fundamentele relaties tussen multidimensionale subshifts. Een subshift is een verzameling kleuringen van een $d$ -dimensionaal rooster ( $\mathbb{Z}^d$ ) met een eindige alfabet, waarbij bepaalde verboden patronen niet mogen voorkomen. De auteurs focussen op twee klassen:

Subshifts van eindig type (SFT): Gedefinieerd door een eindige verzameling verboden patronen.
Effectieve subshifts: Gedefinieerd door een recursief oplosbare (recursively enumerable) verzameling verboden patronen.

De onderzochte relaties zijn:

Gelijkheid ( $X = Y$ )
Conjugatie ( $X \simeq Y$ , een continue shift-equivariante bijectie)
Inclusie ( $X \subseteq Y$ )
Inbedding ( $X \hookrightarrow Y$ , een continue shift-equivariante injectie)

De Parametriseerde Benadering:
In tegenstelling tot eerdere werken (zoals Jeandel en Vanier) die deze problemen behandelden als twee-ingangsproblemen (waarbij zowel $X$ als $Y$ input zijn), fixeren de auteurs hier één subshift $Y$ als parameter en beschouwen ze de andere subshift $X$ als input.

Doel: Begrijpen hoe de dynamische eigenschappen van de parameter $Y$ (zoals periodiciteit, minimaliteit, eindig type, etc.) de computatiecomplexiteit van het probleem beïnvloeden.
Input: $X$ kan een SFT zijn of een effectieve subshift.

2. Methodologie

De auteurs combineren technieken uit de dynamische systemen en de recursietheorie (computability theory).

Complexiteitsklassen: De resultaten worden geformuleerd binnen de arithmetische hiërarchie ( $\Sigma^0_1, \Pi^0_1, \Sigma^0_2, \Pi^0_2, \Sigma^0_3, D(\Sigma^0_1)$ ).
Reducties: Er worden veelvuldig reducties gebruikt van klassieke onbeslisbare problemen zoals:
- Halt (Stopt een Turingmachine op lege input? $\Sigma^0_1$ -compleet).
- Total (Stopt een Turingmachine op alle inputs? $\Pi^0_2$ -compleet).
- COF (Heeft een Turingmachine een cofinite taal? $\Sigma^0_3$ -compleet).
- Het Domino-probleem (Is een SFT niet leeg?).
Constructies: De auteurs construeren specifieke SFT's die Turingmachines simuleren (gebaseerd op het werk van Hao Wang en de Robinson SFT) om de complexiteit van de relaties te manipuleren.
Dynamische Eigenschappen: Er wordt geanalyseerd hoe eigenschappen zoals "minimaal zijn", "eindig zijn", of "computable taal hebben" de complexiteit veranderen.

3. Belangrijkste Bijdragen en Resultaten

De paper is opgedeeld in secties die specifieke problemen behandelen. Hieronder de kernresultaten:

A. Inclusie: $Y \subseteq X$

SFT-inputs: Het probleem is decibel als en slechts als de taal van $Y$ ( $L(Y)$ ) computabel is. De complexiteit is equivalent aan het tellen van de complementaire taal $L(Y)^c$ .
Effectieve inputs: Het probleem is $\Pi^0_2$ -compleet voor een specifieke keuze van $Y$ .
Significantie: Dit toont aan dat er niet-triviale decibele gevallen zijn voor SFT-inputs, wat de "moeras van onbeslisbaarheid" (swamp of undecidability) voor SFT's nuanceert.

B. Inbedding: $Y \hookrightarrow X$

SFT-inputs:
- Als $Y$ een eindige subshift is, is het probleem decibel.
- Als $Y$ een configuratie bevat die "bijna periodiek" is (periodiek behalve in een eindig gebied), is het probleem $\Sigma^0_1$ -hard (onbeslisbaar).
- Verrassend resultaat: Er bestaat een effectieve subshift $Y$ waarvoor $Y \hookrightarrow X$ decibel is voor SFT-inputs, terwijl $L(Y)$ niet computabel is (en dus $Y \subseteq X$ onbeslisbaar is). Dit betekent dat inbedding soms makkelijker kan zijn dan inclusie.
Effectieve inputs: Het probleem is altijd onbeslisbaar ( $\Pi^0_1$ -hard).

C. Inclusie en Inbedding: $X \subseteq Y$ en $X \hookrightarrow Y$

Hier is $Y$ de parameter en $X$ de input.

Als $Y$ een SFT is: Beide problemen zijn $\Sigma^0_1$ -compleet.
Als $Y$ effectief is (maar geen SFT):
- $X \subseteq Y$ kan $\Pi^0_2$ -compleet zijn.
- $X \hookrightarrow Y$ kan $\Sigma^0_3$ -compleet zijn.
Voorwaarde voor lagere complexiteit: Als $Y$ slechts eindig veel SFT-subsystemen bevat, dalen beide problemen naar $\Sigma^0_1$ -compleet.

D. Gelijkheid: $X = Y$

SFT-inputs: Als $Y$ een SFT is, is het probleem $\Sigma^0_1$ -compleet (tenzij $Y$ geen SFT is, dan is het triviaal "nee").
Effectieve inputs:
- De complexiteit ligt tussen $D(\Sigma^0_1)$ en $\Pi^0_2$ .
- Als $Y$ een SFT is met een computabele taal, is het probleem $D(\Sigma^0_1)$ -compleet.
- Als $Y$ geen SFT is, is het probleem $\Pi^0_2$ -compleet.
Conclusie: In dimensie 1 karakteriseert de complexiteit van de gelijkheidsproblemen precies welke effectieve subshifts SFT's zijn.

E. Conjugatie: $X \simeq Y$

SFT-inputs: Altijd $\Sigma^0_1$ -compleet (onbeslisbaar) voor $d \ge 2$ .
Effectieve inputs: De complexiteit varieert sterk afhankelijk van $Y$ $Y$ :
- Bovenste grens: Er bestaat een SFT $Y$ waarvoor het probleem $\Sigma^0_3$ -compleet is.
- Onderste grens: Als $Y$ een SFT is die "minimaal is voor een $\Pi^0_1$ eigenschap" (bijv. een minimale subshift of een volledige subshift), dan is het probleem $D(\Sigma^0_1)$ -compleet.
Koppeling met recente literatuur: De resultaten tonen een verband met het concept van "computable language". Een SFT heeft een computabele taal dan en slechts dan als het minimaal is voor een $\Pi^0_1$ eigenschap. Echter, deze eigenschap is niet altijd conjugatie-invariant, wat betekent dat de complexiteit van het conjugatieprobleem niet altijd door deze eigenschap bepaald kan worden.

4. Dimensie 1 vs. Dimensie $\ge 2$

Dimensie 1: Veel problemen zijn decibel voor SFT-inputs (bijv. gelijkheid en inclusie). De conjugatieprobleem voor SFT's in dimensie 1 blijft een open vraag, maar de auteurs tonen aan dat inbedding voor bepaalde klassen (zoals NMC SFTs) decibel is.
Dimensie $\ge 2$ : Hier domineert de onbeslisbaarheid. De auteurs gebruiken lift-technieken om resultaten uit dimensie 1 naar hogere dimensies te transporteren, maar benadrukken dat de complexiteit in dimensie 2 vaak maximaal is.

5. Significatie en Conclusie

Deze studie biedt een verfijnd inzicht in de relatie tussen dynamische eigenschappen en computatiecomplexiteit:

Nuancering van onbeslisbaarheid: Hoewel de meeste eigenschappen van SFT's onbeslisbaar zijn, identificeert de paper specifieke, niet-triviale gevallen waar problemen decibel zijn (bijv. $Y \hookrightarrow X$ voor eindige $Y$ ).
Asymmetrie: Er is een duidelijke asymmetrie tussen de problemen $X \subseteq Y$ en $Y \subseteq X$ (en analoog voor inbedding). De complexiteit hangt sterk af van welke subshift als parameter wordt gekozen.
Parametriseerde Complexiteit: Door één subshift te fixeren, kunnen de auteurs preciezer karakteriseren welke dynamische eigenschappen (zoals periodiciteit of minimaliteit) verantwoordelijk zijn voor de hoge complexiteit.
Verbinding met Computability: De paper legt een sterke link tussen de complexiteit van het conjugatieprobleem en de eigenschap van een subshift om een "computable language" te hebben, en toont aan dat conjugatie-invariantie hierin een cruciale, maar niet gegarandeerde, rol speelt.

Toekomstperspectief: De auteurs suggereren dat verdere studie nodig is naar de relatie tussen factorafbeeldingen en complexiteit, en of de bevindingen kunnen worden uitgebreid naar subshifts over andere eindig gegenereerde groepen.

Kortom, dit werk levert een grondige classificatie van de rekenkundige moeilijkheidsgraad van vergelijkingen tussen subshifts, afhankelijk van de dynamische aard van de parameter, en biedt een brug tussen de theorie van dynamische systemen en de theoretische informatica.