### Complexity of tile rotation problems

**Keywords:**
rotation, polynomials, theorem, complexity, problems, problem, solving, Computational, proving, Tile

### Abstract

In this paper we introduce tile rotation problems. The instances (or initial configurations) are tile assignments on a (n x n) lattice board, and the question to be answered is the following: does there exist any configuration obtained from the initial one by tile rotations only whose cost is less than a given bound? (notice that a zero-cost configuration corresponds to a perfect tiling). We prove here the NP-completeness for both the zero-cost problem (for a particular set of 5 tiles) and the minimization problem (for a particular set of 2 tiles). Finally, by showing the polynomiality of some subproblems, we establish complexity border results.

### Más información

Título de la Revista: | THEORETICAL COMPUTER SCIENCE |

Volumen: | 188 |

Número: | 1-2 |

Editorial: | Elsevier |

Fecha de publicación: | 1997 |

Página de inicio: | 129 |

Página final: | 159 |

URL: | http://www.scopus.com/inward/record.url?eid=2-s2.0-0031270477&partnerID=q2rCbXpz |