NP-Completeness and Physical Zero-Knowledge Proofs for Zeiger

Abstract

Zeiger is a pencil puzzle consisting of a rectangular grid, with each cell having an arrow pointing in horizontal or vertical direction. Some cells also contain a positive integer. The objective of this puzzle is to fill a positive integer into every unnumbered cell such that the integer in each cell is equal to the number of different integers in all cells along the direction an arrow in that cell points to. In this paper, we prove that deciding solvability of a given Zeiger puzzle is NP-complete via a reduction from the not-all-equal positive 3SAT (NAE3SAT+) problem. We also construct a card-based physical zero-knowledge proof protocol for Zeiger, which enables a prover to physically show a verifier the existence of the puzzle's solution without revealing it.

This paper has appeared at WALCOM 2025

References in corpus (7)

• Physical Zero-Knowledge Proof for Numberlink Puzzle and $k$ Vertex-Disjoint Paths Problem
• Securely Computing the $n$-Variable Equality Function with $2n$ Cards
• Physical Zero-Knowledge Proof for Ripple Effect
• An Improved Physical ZKP for Nonogram and Nonogram Color
• Printing Protocol: Physical ZKPs for Decomposition Puzzles
• Verifying the First Nonzero Term: Physical ZKPs for ABC End View, Goishi Hiroi, and Toichika
• Card-Based Overwriting Protocol for Equality Function and Applications