{"entities":{"Q660171":{"pageid":662020,"ns":120,"title":"Item:Q660171","lastrevid":51411560,"modified":"2026-01-18T03:15:35Z","type":"item","id":"Q660171","labels":{"en":{"language":"en","value":"Minesweeper may not be NP-complete but is hard nonetheless"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6002565"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q660171$30AE3BA9-A3BA-4E3B-90F1-BF1BD1352BEB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"52354a2c93718a999246e14fe15527fdcf90c3d9","datavalue":{"value":{"text":"Minesweeper may not be NP-complete but is hard nonetheless","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q660171$48878139-F22D-499F-BC38-66B45EA078E3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f2e6989c2ab95139d8a99b8af9954ebf51826a1a","datavalue":{"value":"1248.68223","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q660171$F0769037-EAB2-4BE5-A08C-C1057F8D74B4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"76f2bb6abc14b26ed646ec356e1cc195d0d43957","datavalue":{"value":{"entity-type":"item","numeric-id":477689,"id":"Q477689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q660171$3CC27C4A-16CC-4C05-82E2-FE6383E0D5A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f9a47a9ea5068cbd50d30dc8b3bce44f6a76ece5","datavalue":{"value":{"entity-type":"item","numeric-id":456694,"id":"Q456694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q660171$2F6E344F-7900-4F2A-93D0-121565055B0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"62361ae2145ebc2c7cc0c1fe1bcb924d6db25337","datavalue":{"value":{"entity-type":"item","numeric-id":383034,"id":"Q383034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q660171$473622AF-8365-4DB4-8E43-2A1735CDBD38","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7fb1fb9e3613de38b550373bd0384fba28a5a775","datavalue":{"value":{"entity-type":"item","numeric-id":215534,"id":"Q215534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q660171$34B24FD1-AADD-41C7-8219-5EF4568190E1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b7815803d3cf9714123d7f4ecafbad37af479bf0","datavalue":{"value":{"time":"+2012-01-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q660171$F0EB51EE-519D-4BB7-A8C4-2D26B7C61F58","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"84a8a9c13c1deb1f639edbdf3c45218354ced0a0","datavalue":{"value":"Minesweeper is a widely known computer game in which the player has to locate hidden mines on a board of squares. In a famous article, R. Kaye proved that the consistency problem for minesweeper is NP-complete. This is the problem, given a board showing in some squares mines and in some other squares numbers corresponding to the number of neighbouring mines, to determine if it describes an actual minesweeper configuration. Kaye very nicely develops gadgets that simulate wires and switching gates on the board, leading to a reduction of the NP-complete satisfiability problem for propositional formulas, SAT, to the minesweeper consistency problem.  In the present paper it is shown that the following problem is coNP-complete: Given a consistent board, is there at least one square whose content (mine or empty) can be inferred?","type":"string"},"datatype":"string"},"type":"statement","id":"Q660171$A8A85F61-50CF-4935-8F49-56D2692CE498","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9cda603722202722f19339c0e84295bbe19098fb","datavalue":{"value":{"entity-type":"item","numeric-id":208765,"id":"Q208765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q660171$3B0545FB-7F7C-48C7-AAE7-5BA82CD6961E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q660171$28EBB750-C492-4FE3-A91A-37D9D9FC6251","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q660171$F762A068-DC60-4AF7-A5B3-561E612DE070","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d14fcde584dfb5c706e3aafa6df5fc53197017cb","datavalue":{"value":"97A20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q660171$9E904F94-9C34-47E3-8104-2D548C206727","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9b7aa78ffc8274f7d3d6a8d80b152ccccd38ccc4","datavalue":{"value":"6002565","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q660171$BD5E321A-847D-475E-AD59-E2F9FE0BB860","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59a75352ce0c4ced917f372596e545971991ea4f","datavalue":{"value":"Minesweeper","type":"string"},"datatype":"string"},"type":"statement","id":"Q660171$B6EBC55C-8DAD-4FC1-8A54-7F0E674E7299","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q660171$013665B6-9CFB-45DD-B165-219D85330228","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q660171$2CDE12D6-E8E6-489B-ADB1-D1638E6CDE00","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"ae4f1cf8506150645295d9983fde3a89909e3077","datavalue":{"value":"Q63285632","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q660171$3FF302E8-75C9-4893-B65A-3212EEDD1C98","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q660171$F616F574-B409-4582-B369-0605A9B3ABD1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8a9939923180411c33753309486ac58fefc79350","datavalue":{"value":"https://doi.org/10.1007/s00283-011-9256-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q660171$F8FC5132-2466-4302-97D4-E34F88D96349","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6183e14d9958375669a71e3d314d113c7a06720c","datavalue":{"value":"W2126010852","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q660171$57FA9E96-D73A-4D1C-A645-D7786741D2C3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e005b0664e8badef1f76df315bf3df735e8c2118","datavalue":{"value":"10.1007/S00283-011-9256-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q660171$3F053C62-1904-452B-B937-367BD1CD0C68","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"59c15387fbde38a199fcab8a48f6922922758f6a","datavalue":{"value":{"entity-type":"item","numeric-id":632908,"id":"Q632908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c9a389ca5d7e52e1ec8054f40adaaae8f628064","datavalue":{"value":{"amount":"+0.8749018907546997","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q660171$ECD0EBCE-9E71-4F73-9860-DD3FB56AB6DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"511cc0c7b6fcc2c2a079210210d746bcff0e6ba2","datavalue":{"value":{"entity-type":"item","numeric-id":6487580,"id":"Q6487580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"637b96a0c4f8d527f236d37fa37580fac9ba5c80","datavalue":{"value":{"amount":"+0.8387143611907959","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q660171$877180E4-DB03-4DC5-AFEB-9657A0D0375F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b25abb2d8c188b17e3efe211a75ac15c4134ca58","datavalue":{"value":{"entity-type":"item","numeric-id":6487590,"id":"Q6487590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e41b87b78b5ef4b454dfbd81ba852d1f67702794","datavalue":{"value":{"amount":"+0.8156333565711975","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q660171$911114E2-D62A-48E8-B5E5-67F61EFC27E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f282bc97760463a52c009178423b74040317485","datavalue":{"value":{"entity-type":"item","numeric-id":4265945,"id":"Q4265945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ab800cbb236f22e060a568fa1d6698a096a0581","datavalue":{"value":{"amount":"+0.7809868454933167","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q660171$4495295C-181B-4FCB-8FF5-5505C9ECAB18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dbbc8e9249fdd0ac63c5b1a318203f29cf3a68e3","datavalue":{"value":{"entity-type":"item","numeric-id":3060298,"id":"Q3060298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ab800cbb236f22e060a568fa1d6698a096a0581","datavalue":{"value":{"amount":"+0.7809868454933167","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q660171$85E77610-AB0A-4952-A7E4-2FDD1930C367","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:660171","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:660171"}}}}}