The fewest clues problem

DOI10.1016/J.TCS.2018.01.020zbMath1403.68080OpenAlexW2789532453MaRDI QIDQ1623268

Ariel Schvartzman, Erik D. Demaine, Erik Waingarten, Scott Aaronson, Fermi Ma

Publication date: 23 November 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1721.1/123865

zbMATH Keywords

computational complexityhardness reductionspencil-and-paper puzzles

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46)

Cites Work

• The complexity of computing the permanent
• The complexity of completing partial Latin squares
• NP is as easy as detecting unique solutions
• PP is as Hard as the Polynomial-Time Hierarchy
• The Complexity of Enumeration and Reliability Problems
• The NP-Completeness of Some Edge-Partition Problems
• Planar Formulae and Their Uses
• The Complexity of Planar Counting Problems
• Unnamed Item

This page was built for publication: The fewest clues problem