Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players
| Autor: | Bosboom, Jeffrey, Chen, Charlotte, Chung, Lily, Compton, Spencer, Coulombe, Michael, Demaine, Erik D., Demaine, Martin L., Filho, Ivan Tadeu Ferreira Antunes, Hendrickson, Dylan, Hesterberg, Adam, Hsu, Calvin, Hu, William, Korten, Oliver, Luo, Zhezheng, Zhang, Lillian |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: 29 pages, 18 figures. Thorough revisions of Sections 4, 5, and 6/7 (merged) |
| Databáze: | arXiv |
| Externí odkaz: |
|