Cosa significa "Problema del Domino"?
Indice
Il problema del domino è una questione della teoria delle piastrelle che chiede se è possibile coprire un'intera superficie piana usando un dato insieme di piastrelle seguendo regole specifiche.
Piastrelle di Wang
Un tipo comune di piastrella usata in questo problema è la piastrella di Wang. Queste sono piastrelle quadrate che hanno colori sui loro bordi. Le piastrelle possono essere messe l'una accanto all'altra solo se i colori sui bordi che si toccano coincidono.
Decidibilità
In generale, si sa che il problema del domino è indecidibile, il che significa che non c'è un metodo unico che funzioni per ogni possibile situazione. Tuttavia, per un gruppo speciale di piastrelle chiamate piastrelle robuste, il problema può essere risolto. Le piastrelle robuste o non riescono a coprire il piano oppure possono farlo solo in condizioni specifiche.
Piastrelle Non Periodiche
C'è un nuovo tipo di piastrellatura con piastrelle quadrate che non si ripete in un modello regolare. Questo metodo usa regole locali semplici, il che rende facile capire perché queste piastrelle non formino un modello ripetitivo.
Gruppi Iperbolici
In un contesto diverso, per alcuni gruppi noti come gruppi iperbolici, è stato dimostrato che non esiste un metodo per determinare se una collezione di domino può coprire una struttura complessa chiamata grafo di Cayley, specialmente quando i colori devono coincidere nei punti in cui gli spigoli si incontrano. Questo mette in evidenza la complessità e la sfida nel risolvere il problema del domino in vari scenari.