close
Jump to content

minesweeper

From Wiktionary, the free dictionary

English

[edit]
Image
a minesweeper (sense 1.1, in ship form)
Image
a minesweeper (sense 1.1, in helicopter-borne sled form
Image
minesweeper (sense 2)

Etymology

[edit]

From mine +‎ sweeper.

Pronunciation

[edit]

Noun

[edit]

minesweeper (countable and uncountable, plural minesweepers)

  2. A vehicle, device, or person with the purpose of removing explosive mines (landmines or naval mines).
    Antonym: minelayer
    2. (often specifically) A ship specializing in removing naval mines.
      Antonym: minelayer
      Hypernyms: ship < watercraft, vessel < vessel < vehicle
      Hyponym: destroyer minesweeper
      Coordinate term: minehunter
  4. (uncountable, computing, video games) Any of various logic-based computer games in which the player has to discover the position of mines in a rectangular grid, based on numerical hints.
    Coordinate term: battleship
    • 2022, Alex Thieme, Twan Basten, “Minesweeper is Difficult Indeed!: Technology Scaling for Minesweeper Circuits”, in Mariëlle Stoelinga, Nils Jansen, Petra van den Bos, editors, A Journey from Process Algebra Via Timed Automata to Model Learning: Essays Dedicated to Frits Vaandrager on the Occasion of His 60th Birthday [a festschrift⁠]‎[1], Springer Nature Switzerland, →ISBN, page 474:
      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.

Derived terms

[edit]

Translations

[edit]

References

[edit]
Retrieved from "https://en.wiktionary.org/w/index.php?title=minesweeper&oldid=90450233"