Content deleted Content added
m Minor fix |
→Minesweeper Inference Problem: hint to crossover implementation by xor gates |
||
Line 33:
=== Minesweeper Inference Problem ===
This problem asks whether it is possible to locate all the bombs given a [[Minesweeper (video game)|Minesweeper]] board. It has been proven to be [[Co-NP-complete|CoNP-Complete]] via a reduction from Circuit UNSAT problem.<ref>{{Cite journal|last=Scott|first=Allan|last2=Stege|first2=Ulrike|last3=van Rooij|first3=Iris|date=2011-12-01|title=Minesweeper May Not Be NP-Complete but Is Hard Nonetheless|journal=The Mathematical Intelligencer|language=en|volume=33|issue=4|pages=5–17|doi=10.1007/s00283-011-9256-x|issn=1866-7414}}</ref> The gadgets constructed for this reduction are: wire, split, AND and NOT gates and terminator.<ref>{{Cite book|url=http://simon.bailey.at/random/kaye.minesweeper.pdf|title=Minesweeper is NP-complete|last=Kaye|first=Richard}}</ref> There are three crucial observations regarding these gadgets. First, the split gadget can also be used as the NOT gadget and the turn gadget. Second, constructing AND and NOT gadgets is sufficient, because together they can simulate the universal NAND gate. Finally, since we can simulate XOR with three NANDs, and since XOR is enough to build a crossover,<ref>see [[:File:Crossover xor.gif]]</ref> this gives us the needed crossover gadget.
==The Tseytin transformation==
| |||