标题： 关于凸格点多面体的单模同构问题 显示英文标题

标题： On the Unimodular Isomorphism Problem of Convex Lattice Polytopes

摘要： 本文研究了凸格点多面体的\emph{单模同构问题}（UIP）：给定两个凸格点多面体$P$和$P'$，判断是否存在一个单模仿射变换将$P$映射到$P'$。 我们证明了 UIP 是图同构难题，而多面体合同问题和组合多面体同构问题（Akutsu，1998；Kaibel，Schwartz，2003）已被证明是图同构完全问题，同时格点同构问题（$\mathrm{Sikiri\acute{c}}$，$\mathrm{Sch\ddot{u}rmann}$，Vallentin，2009）和射影/仿射多面体同构问题（Kaibel，Schwartz，2003）也被证明是图同构难题。 此外，受格点（非）同构协议（Ducas，van Woerden，2022；Haviv，Regev，2014）的启发，我们为格点多面体的单模同构提出了一个统计零知识证明系统。 最后，我们提出了一种算法，给定两个格点多面体可以计算出所有将一个多面体映射到另一个多面体的单模仿射变换，并且特别地可以判断 UIP。 显示英文摘要

摘要： This paper studies the \emph{unimodular isomorphism problem} (UIP) of convex lattice polytopes: given two convex lattice polytopes $P$ and $P'$, decide whether there exists a unimodular affine transformation mapping $P$ to $P'$. We show that UIP is graph isomorphism hard, while the polytope congruence problem and the combinatorial polytope isomorphism problem (Akutsu, 1998; Kaibel, Schwartz, 2003) were shown to be graph isomorphism complete, and both the lattice isomorphism problem ( $\mathrm{Sikiri\acute{c}}$, $\mathrm{Sch\ddot{u}rmann}$, Vallentin, 2009) and the projective/affine polytope isomorphism problem (Kaibel, Schwartz, 2003) were shown to be graph isomorphism hard. Furthermore, inspired by protocols for lattice (non-) isomorphism (Ducas, van Woerden, 2022; Haviv, Regev, 2014), we present a statistical zero-knowledge proof system for unimodular isomorphism of lattice polytopes. Finally, we propose an algorithm that given two lattice polytopes computes all unimodular affine transformations mapping one polytope to another and, in particular, decides UIP.