{'fraction_non_alphanumeric': 0.02247191011235955, 'fraction_numerical': 0.0007022471910112359, 'mean_word_length': 4.72289156626506, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Computational Complexity of One-Dimensional Origami and Its Application to Digital Signature

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 finding 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 creaserestore problem.