Paper by Erik D. Demaine
- Erik D. Demaine, Fermi Ma, Erik Waingarten, Ariel Schvartzman, and Scott Aaronson, “The Fewest Clues Problem”, Theoretical Computer Science, volume 748, November 2018, pages 28–39.
When analyzing the computational complexity of well-known puzzles, most papers
consider the algorithmic challenge of solving a given instance of (a
generalized form of) the puzzle. We take a different approach by analyzing
the computational complexity of designing a “good” puzzle. We
assume a puzzle maker designs part of an instance, but before publishing it,
wants to ensure that the puzzle has a unique solution. Given a puzzle, we
introduce the FCP (fewest clues
problem) version of the problem:
Given an instance to a puzzle, what is the minimum number of clues we must add in order to make the instance uniquely solvable?
We analyze this question for the Nikoli puzzles Sudoku, Shakashaka, and Akari.
Solving these puzzles is NP-complete, and we show their FCP
versions are Σ2P-complete. Along the way, we show that the
FCP versions of Triangle Partition, Planar 1-in-3
SAT, and Latin Square are all Σ2P-complete. We show
that even problems in P have difficult FCP versions,
sometimes even Σ2P-complete, though “closed under cluing”
problems are in the (presumably) smaller class NP; for example,
FCP 2SAT is NP-complete.
- This paper is also available from ScienceDirect.
- The paper is available in PDF (560k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- FewestClues_FUN2016 (The Fewest Clues Problem)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated June 27, 2019 by