Checking saved dictionary data and trusted language sources. This will stop automatically if a source does not respond.
/ˈmaɪnˌswipɚ/ · noun
A vehicle, device, or person with the purpose of removing explosive mines (landmines or naval mines)..
Information on the history of minesweeper and the rules of the game can be found on Wikipedia [14]. The book by Garey and Johnson [4] is the classical text on NP-completeness. Boolean satisfiability, SAT, is the original decision problem shown NP-complete by Cook [2]. […] Kaye [6] introduced minesweeper consistency and showed its NP-completeness through reduction from circuit-SAT. Kaye's circuit templates are quite involved. An and gate, for instance, has 23 × 13 squares and a wire crossing is built from and and not gates (24 in total). He later published some further, simplified templates [7), but they remain quite large. Kaye's reduction from circuit-SAT to minesweeper does not guarantee a predefined number of hidden mines. We re-establish the NP-completeness of minesweeper consistency by reduction from SAT for the original version of minesweeper with a given number of hidden mines. This illustrates that this extra piece of information does not fundamentally simplify minesweeper. The latter was also already observed by Scott et al. [8]. Scott et al. argue that Kaye's reasoning does not prove NP-completeness of playing minesweeper. Kaye assumed that minesweeper is played by iteratively solving minesweeper consistency. Scott et al. observe that there may be other strategies to play minesweeper. They therefore introduce the minesweeper inference problem, which precisely captures the essence of minesweeper game play. They show that minesweeper inference is co-NP-complete (and hence that playing minesweeper is most likely not NP-complete). They do so by reducing UNSAT to minesweeper inference, for the original version of minesweeper with a given number of hidden mines.
Use minesweeper when its meaning, tone and grammar fit the full sentence. A synonym is not always a direct replacement.
Minesweeper means A vehicle, device, or person with the purpose of removing explosive mines (landmines or naval mines)..
The closest synonym depends on the sentence and intended sense.
Possible antonyms include minelayer.
Information on the history of minesweeper and the rules of the game can be found on Wikipedia [14]. The book by Garey and Johnson [4] is the classical text on NP-completeness. Boolean satisfiability, SAT, is the original decision problem shown NP-complete by Cook [2]. […] Kaye [6] introduced minesweeper consistency and showed its NP-completeness through reduction from circuit-SAT. Kaye's circuit templates are quite involved. An and gate, for instance, has 23 × 13 squares and a wire crossing is built from and and not gates (24 in total). He later published some further, simplified templates [7), but they remain quite large. Kaye's reduction from circuit-SAT to minesweeper does not guarantee a predefined number of hidden mines. We re-establish the NP-completeness of minesweeper consistency by reduction from SAT for the original version of minesweeper with a given number of hidden mines. This illustrates that this extra piece of information does not fundamentally simplify minesweeper. The latter was also already observed by Scott et al. [8]. Scott et al. argue that Kaye's reasoning does not prove NP-completeness of playing minesweeper. Kaye assumed that minesweeper is played by iteratively solving minesweeper consistency. Scott et al. observe that there may be other strategies to play minesweeper. They therefore introduce the minesweeper inference problem, which precisely captures the essence of minesweeper game play. They show that minesweeper inference is co-NP-complete (and hence that playing minesweeper is most likely not NP-complete). They do so by reducing UNSAT to minesweeper inference, for the original version of minesweeper with a given number of hidden mines.
FreeDictionaryAPI.com / Wiktionary · Original source · CC BY-SA 4.0
Dictionary data is provided by FreeDictionaryAPI.com and sourced from Wiktionary under its stated license.