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.


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.