Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants
<|reference_start|>Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants: We study three problems related to the computational complexity of the popular game Minesweeper. The first is consistency: given a set of clues, is there any arrangement of mines that satisfies it? This problem has been known to be NP-complete since 2000, but our framework proves it as a side effect. The second is inference: given a set of clues, is there any cell that the player can prove is safe? The coNP-completeness of this problem has been in the literature since 2011, but we discovered a flaw that we believe is present in all published results, and we provide a fixed proof. Finally, the third is solvability: given the full state of a Minesweeper game, can the player win the game by safely clicking all non-mine cells? This problem has not yet been studied, and we prove that it is coNP-complete.<|reference_end|>
@article{mit hardness group2024complexity,
    title={Complexity of Planar Graph Orientation Consistency, Promise-Inference,
  and Uniqueness, with Applications to Minesweeper Variants},
    author={MIT Hardness Group, Della Hendrickson, Andy Tockman},
    journal={arXiv preprint arXiv:2404.14519},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.14519},
    primaryClass={cs.CC}
}