Combinatorial Optimization in Pattern Assembly - (Extended Abstract)
Combinatorial Optimization in Pattern Assembly - (Extended Abstract)
复制标题
模式组装中的组合优化 -（扩展摘要）
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Shinnosuke Seki
中科院分区：
文献类型：
--
作者：
Shinnosuke Seki
图案自组装瓦集综合是一个np困难组合问题，其目的是最小化能唯一自组装给定矩形图案的直线瓦集系统（RTAS）。当c≥1时，c-Pats是Pats的一个子问题，只接受最多c种颜色的图案作为输入。为了证明60-Pats是np困难的，我们提出将3Sat的多项式时间约简为60-Pats。
Pattern self-assembly tile set synthesis (Pats) is an NP-hard combinatorial problem to minimize a rectilinear tile assembly system (RTAS) that uniquely self-assembles a given rectangular pattern. For c ≥ 1, c-Pats is a subproblem of Pats which takes only the patterns with at most c colors as input. We propose a polynomial-time reduction of 3Sat to 60-Pats in order to prove that 60-Pats is NP-hard.