期刊
ALGORITHMS
卷 5, 期 1, 页码 148-157出版社
MDPI AG
DOI: 10.3390/a5010148
关键词
computational complexity; interlocked polygons; monotone boolean function; sliding block puzzle
资金
- Grants-in-Aid for Scientific Research [23500013] Funding Source: KAKEN
Suppose there is a collection of n simple polygons in the plane, none of which overlap each other. The polygons are interlocked if no subset can be separated arbitrarily far from the rest. It is natural to ask the characterization of the subsets that makes the set of interlocked polygons free (not interlocked). This abstracts the essence of a kind of sliding block puzzle. We show that any monotone Boolean function f on n variables can be described by in = O(n) interlocked polygons. We also show that the decision problem that asks if given polygons are interlocked is PSPACE-complete.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据