1
$\begingroup$

Given a board of size $n \times 1$ where $n=\infty$ (basically a tape, one way infinite), and a set of colors $C$, some starting color $c_{start} \in C$, a set of templates $T$ in a form $(c_k, i, c_i, j, c_j)$ (meaning if on some position on the board there is a color $c_k$ then $i$ steps to the right of $c_k$ there is a color $c_i$, and $j$ steps to the right of $c_i$ there is a color $c_j$).

Prove that if we put $c_{start}$ on the board in position $(1,1)$ (furthest to the left), the answer to the question below is PSPACE-hard

Can we fill the board with $c \in C$ in such a way that we use all the elements from $T$?

I attempted to reduce TQBF to this problem, however if I construct a gadget where I say that each variable is a color, I have a trouble encoding $i$ and $j$ with clauses. Also, I'm not sure if it's the right direction (maybe try reducing from GG? but I would have the same problem).

Any help is appreciated.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.