To show that is also the lower bound for the complexity of consistency, we use a bounded version of the domino problem. Domino problems [Wan63,Ber66] have successfully been employed to establish undecidability and complexity results for various description and modal logics [Spa93,BS99].