Direkt zum Inhalt

Lexikon der Mathematik: Dominoproblem

ein algorithmisches Entscheidungsproblem, bei dem ein Tripel (D, H, V), bestehend aus einer endlichen Menge D von „Dominosteinen“ und einer horizontalen und vertikalen „Nachbarschaftsbeziehung“, gegeben ist, wobei H, VD × D.

Gesucht ist eine D-Parkettierung der Ebene, d. h. eine totale Funktion

\begin{eqnarray}f:{{\mathbb{N}}}_{0}\times {{\mathbb{N}}}_{0}\to D\end{eqnarray}

mit

\begin{eqnarray}f(x,y)Hf(x+1,y)\,\,\,\,{\rm{und}}\,\,\,f(x,y)\,Vf(x,y+1)\end{eqnarray}

für alle x, y ∈ ℕ0.

Das Dominoproblem (also die Frage, ob eine entsprechende Parkettierung existiert) ist nicht entscheidbar (Entscheidbarkeit).

Das Dominoproblem dient oft als Ausgangspunkt, um mit der Methode der Reduktion (many-one Reduzierbarkeit) weitere Probleme, insbesondere aus dem Bereich der Prädikatenlogik, als nicht entscheidbar nachzuweisen.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos