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, V ⊆ D × 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}

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

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.