Spiral Galaxies is a pencil-and-paper puzzle played on a grid of unit squares: given a set of points called centers, the goal is to partition the grid into polyominoes such that each polyomino contains exactly one center and is $180^\circ$ rotationally symmetric about its center. We show that this puzzle is NP-complete even if the polyominoes are restricted to be (a) rectangles of arbitrary size or (b) 1$\times$1, 1$\times$3, and 3$\times$1 rectangles. The proof for the latter variant also implies NP-completeness of finding a non-crossing matching in modified grid graphs where edges connect vertices of distance $2$. Moreover, we prove NP-completeness of the design problem of minimizing the number of centers such that there exist a set of Spiral Galaxies that exactly cover a given shape.


翻译:螺旋星系是一个在单位方格网格上播放的铅笔和纸的拼图 : 如果有一组点称为中心, 目标是将网格分割成多聚人种, 这样每个聚聚虫体就包含一个完全的中枢, 其中心旋转对称为 180 ⁇ circ$ 。 我们显示这个拼图是全 NP 的, 即使多聚人种被限制为 (a) 任意大小的矩形或 (b) 1 $\ times$ 1, 1 $\ times 3 和 3$\ times $ 1 矩形。 后一种变种的证明也意味着在修改的网格图中找到非交叉匹配的 NP, 其中边缘连接距离的脊椎为$2 。 此外, 我们证明在最小化中心数量的设计问题上NP 的完整性, 即最小化中心的数量, 这样有一套正覆盖给定形状的螺旋键。

0
下载
关闭预览

相关内容

【经典书】模式识别导论,561页pdf
专知会员服务
81+阅读 · 2021年6月30日
专知会员服务
123+阅读 · 2020年9月8日
专知会员服务
159+阅读 · 2020年1月16日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
【论文笔记】通俗理解少样本文本分类 (Few-Shot Text Classification) (1)
深度学习自然语言处理
7+阅读 · 2020年4月8日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
开膛手约翰 - 密码破解者
黑白之道
8+阅读 · 2019年2月6日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
BAT机器学习面试题1000题(316~320题)
七月在线实验室
14+阅读 · 2018年1月18日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】GAN架构入门综述(资源汇总)
机器学习研究会
10+阅读 · 2017年9月3日
Arxiv
0+阅读 · 2021年11月23日
Arxiv
0+阅读 · 2021年11月22日
Arxiv
11+阅读 · 2021年3月25日
Arxiv
27+阅读 · 2020年6月19日
VIP会员
相关资讯
【论文笔记】通俗理解少样本文本分类 (Few-Shot Text Classification) (1)
深度学习自然语言处理
7+阅读 · 2020年4月8日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
开膛手约翰 - 密码破解者
黑白之道
8+阅读 · 2019年2月6日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
BAT机器学习面试题1000题(316~320题)
七月在线实验室
14+阅读 · 2018年1月18日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】GAN架构入门综述(资源汇总)
机器学习研究会
10+阅读 · 2017年9月3日
Top
微信扫码咨询专知VIP会员