We show that the decision problem of determining whether a given (abstract simplicial) $k$-complex has a geometric embedding in $\mathbb R^d$ is complete for the Existential Theory of the Reals for all $d\geq 3$ and $k\in\{d-1,d\}$. This implies that the problem is polynomial time equivalent to determining whether a polynomial equation system has a real root. Moreover, this implies NP-hardness and constitutes the first hardness results for the algorithmic problem of geometric embedding (abstract simplicial) complexes.


翻译:我们显示,确定给定(抽象的)$k$-complex是否在$\mathbb R ⁇ d$中嵌入几何分数的决定问题,对于所有$d\geq 3美元和$k\in ⁇ d-1,d ⁇ $,对于真实的Reals理论来说已经完全解决了。这意味着问题在于多元时间,相当于确定多元方程系统是否具有真正的根基。此外,这意味着NP硬性,是几何嵌入(抽象的)复合体的算法问题的第一个硬性结果。

0
下载
关闭预览

相关内容

【图与几何深度学习】Graph and geometric deep learning,49页ppt
专知会员服务
41+阅读 · 2021年4月2日
最新《几何深度学习》教程,100页ppt,Geometric Deep Learning
专知会员服务
100+阅读 · 2020年7月16日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
图神经网络库PyTorch geometric
图与推荐
17+阅读 · 2020年3月22日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
已删除
将门创投
9+阅读 · 2018年12月19日
Arxiv
0+阅读 · 2021年10月5日
Arxiv
0+阅读 · 2021年10月4日
Arxiv
0+阅读 · 2021年10月4日
Arxiv
3+阅读 · 2018年10月18日
VIP会员
相关主题
相关资讯
图神经网络库PyTorch geometric
图与推荐
17+阅读 · 2020年3月22日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
已删除
将门创投
9+阅读 · 2018年12月19日
Top
微信扫码咨询专知VIP会员