報 每日報告新聞網
聖塔非研究所

摘要 眾所周知，給定的有限區域是否可以用給定的一組瓦片進行瓦片的問題是NP完全的

2022-09-02 · 已發表論文 · 更新 2026/03/19 上午04:20

摘要 眾所周知，給定的有限區域是否可以用給定的一組瓦片進行瓦片的問題是NP完全的。我們證明，對於方形格子上的右側特羅米諾和方形四格骨，或者單獨的右側特羅米諾，也是如此。在這個過程中，我們證明了平面三次圖的單調一合三可滿足性是 NP 完全的。在更高維度中，我們展示了立方晶格上一般區域的多米諾骨牌和直特羅米諾骨牌以及四維超立方晶格上的簡單連接區域的 NP 完備性。

SFI 頁面

本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。

原文連結

論文資訊

  • 類型：已發表論文
  • 日期：2022-09-02

摘要

眾所周知，給定的有限區域是否可以用給定的一組瓦片進行瓦片的問題是NP完全的。我們證明，對於方形格子上的右側特羅米諾和方形四格骨，或者單獨的右側特羅米諾，也是如此。在這個過程中，我們證明了平面三次圖的單調一合三可滿足性是 NP 完全的。在更高維度中，我們展示了立方晶格上一般區域的多米諾骨牌和直特羅米諾骨牌以及四維超立方晶格上的簡單連接區域的 NP 完備性。