Back to Search
Start Over
The fewest clues problem
- Source :
- Dagstuhl Publishing, MIT web domain
- Publication Year :
- 2018
- Publisher :
- Elsevier BV, 2018.
-
Abstract
- 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.<br />NSF (Grant DGE-16-44869)
- Subjects :
- Discrete mathematics
Class (set theory)
000 Computer science, knowledge, general works
General Computer Science
Computational complexity theory
Computer science
MathematicsofComputing_GENERAL
020206 networking & telecommunications
02 engineering and technology
Theoretical Computer Science
Shakashaka
Computer Science
0202 electrical engineering, electronic engineering, information engineering
Order (group theory)
Partition (number theory)
020201 artificial intelligence & image processing
Subjects
Details
- ISSN :
- 03043975
- Volume :
- 748
- Database :
- OpenAIRE
- Journal :
- Theoretical Computer Science
- Accession number :
- edsair.doi.dedup.....d1972bae486f0559ff7982c301edc764