Minesweeper Is PP-hard

arXiv > cs > arXiv:1204.4659 Computer Science > Computational Complexity [Submitted on 20 Apr 2012] The computational complexity of Minesweeper Michiel de Bondt We show that the Minesweeper game is PP-hard, when the object is to locate all min the probability of locating all mines may be infinitesimal, the Minesweeper game is ev construction, the player can reveal a boolean circuit in polynomial time, after

A screenshot of an arXiv paper about the computational complexity of Minesweeper, with “PP-hard” highlighted. The joke is that the seemingly simple puzzle is presented with intimidating theoretical-computer-science terminology, making it a reaction image for situations that are unexpectedly complicated or absurdly technical.

• @gentoomemes / 12982 2024-08-26