TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

Tiling with Three Polygons Is Undecidable

136 点作者 denvaar6 个月前

6 条评论

xianshou6 个月前
First you ask how the hell someone could come up with this construction.<p>Then you realize it was this guy: <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Erik_Demaine" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Erik_Demaine</a>
评论 #42191446 未加载
评论 #42193578 未加载
评论 #42191686 未加载
评论 #42190342 未加载
评论 #42189962 未加载
YoumuChan6 个月前
The author gave a talk on this at Tufts during the FWCG last week. Fascinating talk.<p>One interesting question from audience was whether the ratio between the largest polygon piece and the smallest piece can be made bounded, as the current construction has unbounded ratio.
whatshisface6 个月前
That&#x27;s reminicient of the post correspondence problem. Is the PCP still undecidable for sets of three strings?
评论 #42191444 未加载
joebergeron6 个月前
I read the title of this paper and thought to myself, “What are the chances this could be Erik Demaine?”. And sure enough!
bryan06 个月前
While not proven, is the intuition that this will also be undecideable for 1 and 2 polygon tilings?
romwell6 个月前
Erik Demaine always has some fun stuff for us.