NP-Completeness and Physical Zero-Knowledge Proof of Hotaru Beam
Abstract
Hotaru Beam is a logic puzzle which objective is to connect circles placed on a grid by drawing only lines with specified starting points and numbers of bends. A zero-knowledge proof is a communication protocol that allows one player to persuade the other that they are in possession of a certain piece of information without actually revealing it. We show that Hotaru Beam is NP-complete and present a physical zero-knowledge proof (i.e. implementable using physical items) for proving that one knows a solution to the puzzle.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Advanced Graph Theory Research
Cryptography and Data Security
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 2 March 2026
- Language
- EN
- Document type
- Preprint