标题： 拼图的不可判定性 显示英文标题

标题： Undecidability of Tiling with a Tromino

摘要： 给定一个L形或I形三格骨牌的周期性排列，我们证明了判断它是否可以完成为平面铺砌问题是co-RE完全的（因此是不可判定的）。 相比之下，如果初始排列是有限的，或者瓷砖是多米诺骨牌而不是三格骨牌（在任何维度中），则该问题变为可判定的。 作为结果，用给定的三格骨牌（L形或I形）铺砌给定的平面周期子集是co-RE完全的。 我们还证明了用两个多米诺骨牌（其中一个不连通，另一个大小恒定）铺砌整个平面是co-RE完全的，以及用两个连通的多立方体（其中一个大小恒定）铺砌三维空间是co-RE完全的。 如果我们仅限制通过平移进行铺砌（不允许旋转），那么我们得到co-RE完全性需要再多一个瓷砖：二维周期子集需要两个三格骨牌，二维平面需要三个多米诺骨牌，三维空间需要三个连通的多立方体。 在此过程中，我们证明了关于周期性（无限）图的一些新的复杂性和算法结果。 值得注意的是，我们证明了二维中的Periodic Planar (1-in-)3SAT-3、3DM和Graph Orientation是co-RE完全的，而在一维中是PSPACE完全的；我们将图绘制的基本结果扩展到二维周期性图；并且我们给出了二分周期性图中完美匹配的多项式时间算法。 显示英文摘要

摘要： Given a periodic placement of copies of a tromino (either L or I), we prove co-RE-completeness (and hence undecidability) of deciding whether it can be completed to a plane tiling. By contrast, the problem becomes decidable if the initial placement is finite, or if the tile is a domino instead of a tromino (in any dimension). As a consequence, tiling a given periodic subset of the plane with a given tromino (L or I) is co-RE-complete. We also prove co-RE-completeness of tiling the entire plane with two polyominoes (one of which is disconnected and the other of which has constant size), and of tiling 3D space with two connected polycubes (one of which has constant size). If we restrict to tiling by translation only (no rotation), then we obtain co-RE-completeness with one more tile: two trominoes for a periodic subset of 2D, three polyominoes for the 2D plane, and three connected polycubes for 3D space. Along the way, we prove several new complexity and algorithmic results about periodic (infinite) graphs. Notably, we prove that Periodic Planar (1-in-)3SAT-3, 3DM, and Graph Orientation are co-RE-complete in 2D and PSPACE-complete in 1D; we extend basic results in graph drawing to 2D periodic graphs; and we give a polynomial-time algorithm for perfect matching in bipartite periodic graphs.