Computational Complexity of One-Dimensional Origami and Its Application to Digital Signature-猫眼课题宝

DOI：

发表时间：

2022

期刊：

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Junnosuke Hoshido;Tonan Kamata;Tsutomu Ansai;Ryuhei Uehara

我们研究了一个简单的一维折纸问题的计算复杂性。给我们一个长度为n +1的纸条P，并通过在单位间隔处折痕将其折叠成单位长度。因此，一般来说，每个折痕处都有几层纸。每个折痕处的纸层数称为折痕处的折痕宽度。对于给定的P的山谷分配，一般来说，有指数级的许多方法可以将纸张折叠成与分配一致的单位长度。已知找到折叠P的方法以最小化折叠状态的最大折痕宽度的问题是NP完全的。在这项研究中，我们研究了一个相关的折纸问题。对于P的任何给定折叠状态，每个折痕都有其山谷分配和折痕宽度分配。那么，当只给出这些赋值的部分信息时，我们能唯一地恢复折叠态吗？我们引入这个自然的问题作为折痕恢复问题，其中有一些变量取决于有关分配的信息。在本文中，我们证明了一些情况下是多项式时间可解的，一些情况下是强NP-完全的。作为该问题的一个应用，我们还提出了一个基于折痕恢复困难性的数字签名系统。

We investigate the computational complexity of a simple one-dimensional origami problem. We are given a paper strip P of length n +1 and fold it into unit length by creasing at unit intervals. Consequently, we have several paper layers at each crease in general. The number of paper layers at each crease is called the crease width at the crease. For a given mountain-valley assignment of P , in general, there are exponentially many ways of folding the paper into unit length consistent with the assignment. It is known that the problem of ﬁnding a way of folding P to minimize the maximum crease width of the folded state is NP-complete. In this study, we investigate a related paper-folding problem. For any given folded state of P , each crease has its mountain–valley assignment and crease-width assignment. Then, can we restore the folded state uniquely when only partial information about these assignments is given? We introduce this natural problem as the crease-restore problem, for which there are a number of variants depending on the information given about the assignments. In this paper, we show that some cases are polynomial-time solvable and that some cases are strongly NP-complete. As an application of the problem, we also propose a digital signature system based on the hardness of the crease-restore problem.

Computational Complexity of One-Dimensional Origami and Its Application to Digital Signature

文献摘要

相似文献