Minesweeper is Difficult Indeed!: Technology Scaling for Minesweeper Circuits

Alex Thieme; Twan Basten

doi:10.1007/978-3-031-15629-8_25

Minesweeper is Difficult Indeed! Technology Scaling for Minesweeper Circuits

Alex Thieme
, Twan Basten

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

1 Citation (Scopus)

909 Downloads (Pure)

Abstract

Various aspects of playing minesweeper have been proven to be (co-)NP-complete through reductions from circuit-SAT and UNSAT. The proofs use quite involved minesweeper templates to simulate Boolean formulas and circuits. We provide a set of much simpler synthesis templates, leading to much smaller circuit simulations in minesweeper.

Original language	English
Title of host publication	A Journey from Process Algebra via Timed Automata to Model Learning
Subtitle of host publication	Essays Dedicated to Frits Vaandrager on the Occasion of His 60th Birthday
Place of Publication	Cham
Publisher	Springer
Chapter	25
Pages	472-490
Number of pages	19
ISBN (Electronic)	978-3-031-15629-8
ISBN (Print)	978-3-031-15628-1
DOIs	https://doi.org/10.1007/978-3-031-15629-8_25
Publication status	Published - 2022

Publication series

Name	Lecture Notes in Computer Science (LNCS)
Publisher	Springer
Volume	13560
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Keywords

Circuit simulation
Complexity
Games

Access to Document

10.1007/978-3-031-15629-8_25

minesweeper-finalFinal author version , 3.53 MB

Cite this

Thieme, A., & Basten, T. (2022). Minesweeper is Difficult Indeed! Technology Scaling for Minesweeper Circuits. In A Journey from Process Algebra via Timed Automata to Model Learning : Essays Dedicated to Frits Vaandrager on the Occasion of His 60th Birthday (pp. 472-490). (Lecture Notes in Computer Science (LNCS); Vol. 13560). Springer. https://doi.org/10.1007/978-3-031-15629-8_25

@inbook{4679577a7e964ebdac162249f6b4b1f3,

title = "Minesweeper is Difficult Indeed!: Technology Scaling for Minesweeper Circuits",

abstract = "Various aspects of playing minesweeper have been proven to be (co-)NP-complete through reductions from circuit-SAT and UNSAT. The proofs use quite involved minesweeper templates to simulate Boolean formulas and circuits. We provide a set of much simpler synthesis templates, leading to much smaller circuit simulations in minesweeper.",

keywords = "Circuit simulation, Complexity, Games",

author = "Alex Thieme and Twan Basten",

year = "2022",

doi = "10.1007/978-3-031-15629-8\_25",

language = "English",

isbn = "978-3-031-15628-1",

series = "Lecture Notes in Computer Science (LNCS)",

publisher = "Springer",

pages = "472--490",

booktitle = "A Journey from Process Algebra via Timed Automata to Model Learning",

address = "Germany",

}

Thieme, A & Basten, T 2022, Minesweeper is Difficult Indeed! Technology Scaling for Minesweeper Circuits. in A Journey from Process Algebra via Timed Automata to Model Learning : Essays Dedicated to Frits Vaandrager on the Occasion of His 60th Birthday. Lecture Notes in Computer Science (LNCS), vol. 13560, Springer, Cham, pp. 472-490. https://doi.org/10.1007/978-3-031-15629-8_25

Minesweeper is Difficult Indeed! Technology Scaling for Minesweeper Circuits. / Thieme, Alex; Basten, Twan.
A Journey from Process Algebra via Timed Automata to Model Learning : Essays Dedicated to Frits Vaandrager on the Occasion of His 60th Birthday. Cham: Springer, 2022. p. 472-490 (Lecture Notes in Computer Science (LNCS); Vol. 13560).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

TY - CHAP

T1 - Minesweeper is Difficult Indeed!

T2 - Technology Scaling for Minesweeper Circuits

AU - Thieme, Alex

AU - Basten, Twan

PY - 2022

Y1 - 2022

N2 - Various aspects of playing minesweeper have been proven to be (co-)NP-complete through reductions from circuit-SAT and UNSAT. The proofs use quite involved minesweeper templates to simulate Boolean formulas and circuits. We provide a set of much simpler synthesis templates, leading to much smaller circuit simulations in minesweeper.

AB - Various aspects of playing minesweeper have been proven to be (co-)NP-complete through reductions from circuit-SAT and UNSAT. The proofs use quite involved minesweeper templates to simulate Boolean formulas and circuits. We provide a set of much simpler synthesis templates, leading to much smaller circuit simulations in minesweeper.

KW - Circuit simulation

KW - Complexity

KW - Games

UR - https://www.scopus.com/pages/publications/85138207220

U2 - 10.1007/978-3-031-15629-8_25

DO - 10.1007/978-3-031-15629-8_25

M3 - Chapter

AN - SCOPUS:85138207220

SN - 978-3-031-15628-1

T3 - Lecture Notes in Computer Science (LNCS)

SP - 472

EP - 490

BT - A Journey from Process Algebra via Timed Automata to Model Learning

PB - Springer

CY - Cham

ER -