研究成果

学術論文誌

  • NP-Completeness and Physical Zero-Knowledge Proofs for Sumplete, a Puzzle Generated by ChatGPT
    著者
    K. Hatsugai, S. Ruangwises, K. Asano, and Y. Abe
    雑誌名
    New Generation Computing
    出版社
    Springer
    発行年
    2024
    To appear.
    Abstract

    Sumplete is a logic puzzle generated by ChatGPT in March 2023. The puzzle consists of a rectangular grid, with each cell containing an integer. Each row and column also has an integer called target value assigned to it. The objective of this puzzle is to cross out some numbers in the grid such that the sum of uncrossed numbers in each row and column is equal to the corresponding target value. In this paper, we prove that Sumplete is NP-complete. We also propose a physical zero-knowledge proof protocol for the puzzle using physical cards.