Given a set of colors $T = \{1, \ldots, k\}$, a set of horizontal or vertical rules $H, V \subseteq T \times T$ of ordered pairs, and a chosen color $b = 1$, the tiling language is defined as follows:

$$ L = \{n \mid n \text{ is encoded in binary, I can tile an } n \times n \text{ grid with colors of $T$ respecting the horizontal rules } H, \text{ the vertical rules } V, \text{ and placing the boundary conditions } b \text{ at the 4 corners}\} $$

It has been proven that $T$, $b$, $H$, and $V$ exist, such that this language is NEXP-complete (Theorem 2.2 in Section 2 of this paper).

Based on my understanding, in this paper, they take any language $L'\in$ NEXP and reduce it to Tiling problems where the rules are given by the Cook-Levin reduction of the non-deterministic Turing Machine deciding $L'$. This reduction is a bit complicated and poorly interpretable in practice.

My question is: is there another way to prove this? For example, with a natural reduction from one of the succinct languages that is NEXP-complete?

I can't find anything similar in the literature for this specific version of tiling, while for other versions of tiling, such as the one where each tile is divided into 4 quadrants, similar results exist.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.