论文标题
边缘与不平等，三角形，未知形状和两个玩家匹配
Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players
论文作者
论文摘要
我们分析了边缘匹配难题的几种新变体的计算复杂性。首先，我们分析了相邻瓷砖之间的不平等（而不是平等）的约束，证明了严格不平等的问题NP统计数字，但对于非平等性不平等而言。其次，我们分析了三种类型的三角边缘匹配，其中一种是多项式，另一种是NP完整的。这三个都是＃P-Complete。第三，我们分析未指定目标形状的情况，而我们只是想放置（正方形）瓷砖，以使边缘匹配（恰好）；这个问题是NP完成的。第四，我们考虑了基于$ 1 \ times n $ edge匹配的四个2播放器游戏，其中四个都是pspace-complete。我们的大多数NP硬度降低都是简单的，新近证明的#P和ASP完整性，例如$ 1 \ times n $ edge匹配。
We analyze the computational complexity of several new variants of edge-matching puzzles. First we analyze inequality (instead of equality) constraints between adjacent tiles, proving the problem NP-complete for strict inequalities but polynomial for nonstrict inequalities. Second we analyze three types of triangular edge matching, of which one is polynomial and the other two are NP-complete; all three are #P-complete. Third we analyze the case where no target shape is specified, and we merely want to place the (square) tiles so that edges match (exactly); this problem is NP-complete. Fourth we consider four 2-player games based on $1 \times n$ edge matching, all four of which are PSPACE-complete. Most of our NP-hardness reductions are parsimonious, newly proving #P and ASP-completeness for, e.g., $1 \times n$ edge matching.
