{"entities":{"Q6081384":{"pageid":13215691,"ns":120,"title":"Item:Q6081384","lastrevid":39838232,"modified":"2025-01-27T18:10:09Z","type":"item","id":"Q6081384","labels":{"en":{"language":"en","value":"6-uniform Maker-Breaker game is PSPACE-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7745890"}},"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":"Q6081384$6361B930-D916-4091-90F3-D2054CA76E8E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b882102ad756767521c78b05e0df2e7751de148a","datavalue":{"value":{"text":"6-uniform Maker-Breaker game is PSPACE-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6081384$29A1DC82-30EB-49E8-84DC-06283ACCB340","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6081384$1D40358A-5C58-4019-B6B0-8404BB0A0C06","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31c936eef8b332040242af2e27eaff5bc37458f1","datavalue":{"value":{"time":"+2023-10-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6081384$9D4F3EBB-14D8-41EE-B231-B1FC77FE679F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"461b86a6d139f79fec1c250efa841f0a43a83787","datavalue":{"value":"The paper deals with the problem of determining the winner of a Maker-Breaker game. In this kind of game, a set of subsets is given, which elements all belong to a finite universe set. At each turn, one player seizes one element among those that were not selected in previous steps. The Maker wins if he is able to select every element of at least one subset. The Breaker wins if he can select at least one element for each subset. \\par The winner individuation problem was proved PSPACE-complete in a 1976 paper by Schaefer for games in which subsets are bound to have size not exceeding 11. In this paper the authors significantly improve the result by proving the PSPACE-completeness of the problem when the maximum subset size is limited to 6. Moreover, the authors also provide NL-hardness results for some simpler game cases.\\par The paper basically consists of the results, proofs, it is opened by a very nice introduction where the problem is stated and some relevant literature is referred to and is closed by a brief section restating the problem resulting state of the art so that open cases are clearly pinpointed.\\par Overall, a paper certainly worth reading.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6081384$A8389488-E745-4812-9D41-101B1B5AF8B6","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3559891ba10f0312908088570a9d11a4580a41b9","datavalue":{"value":{"entity-type":"item","numeric-id":483300,"id":"Q483300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6081384$3867634F-6F04-42EA-8A34-86346EB4358D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6081384$C1589661-0E52-4B26-9217-E8BE61149E1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6081384$1693A80D-12C5-4747-B849-17F9E28967A8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3dcedce1b35bdf6f1314c8e2ccde1032f015611f","datavalue":{"value":"7745890","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6081384$C6D27626-78B2-4D19-919F-D25CACC39304","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q6081384$BAA3CBC2-F151-4410-AC56-20F2B1325A15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b53c552f034f0759ded21ef7d92b5c6222376092","datavalue":{"value":"game","type":"string"},"datatype":"string"},"type":"statement","id":"Q6081384$5AD482D7-314B-44FC-9BE8-F9001BD2CDA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f87b2e6cd7c475748f54c976b8560f2316797e1","datavalue":{"value":"Maker-Breaker","type":"string"},"datatype":"string"},"type":"statement","id":"Q6081384$3C6740AE-3ABE-4CC2-B648-543AB099C25B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9864c2fab8ff6f6a7cbed64d92db42aebc3ab755","datavalue":{"value":"NL-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q6081384$B0A14BF3-E3AB-47EC-8E5D-B834FBCC1CFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a05cfd9da536bc8387292ab9359d3f7e9902a360","datavalue":{"value":"PSPACE-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q6081384$F4AD79A9-A73D-494D-8763-C38425D82260","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cfc1c912dbc1f534d35dfe4c7b828346e80b5fd8","datavalue":{"value":"reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q6081384$349DDE4F-1EA7-4465-B93A-5807F3CB30C1","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":"Q6081384$81676705-10DF-4B4D-94B9-9CAFFA5A50EA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c0f515cdf9ea5d2d9ac86df7441b24cdd57becb4","datavalue":{"value":"10.1007/S00493-023-00026-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6081384$F31B314D-BFF0-4CA6-9458-F8130BC76203","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a23c5dfdde0976b97075448a1fd993625fb87bda","datavalue":{"value":{"entity-type":"item","numeric-id":776271,"id":"Q776271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd6a5455c663e0cc745514908c50ec62db709051","datavalue":{"value":{"amount":"+0.75711673","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6081384$883B0D8D-BA5B-4EB3-8B86-781AE5CDC332","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d9117a69b9cb3e7fd7baca30cc85771b14b5eea","datavalue":{"value":{"entity-type":"item","numeric-id":2898395,"id":"Q2898395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"102dd0fc0f8eb713b76e661d01428f0db5447004","datavalue":{"value":{"amount":"+0.74787325","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6081384$2E0E7EF8-45C9-4D54-AD7F-25F372753827","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d72649a232ce7f6515886886f83fcaee4e6eff32","datavalue":{"value":{"entity-type":"item","numeric-id":5875715,"id":"Q5875715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f400c0efca92decb5886ca0faa007ef8e4b15ed8","datavalue":{"value":{"amount":"+0.7189842","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6081384$80CD8799-E035-4DD4-B999-AEB93965A225","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51e22e9f222a992b14c93966e1924cb0047bf7d4","datavalue":{"value":{"entity-type":"item","numeric-id":410721,"id":"Q410721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c89163a6359ae3d2baa4a192c270ade4ab46b2a","datavalue":{"value":{"amount":"+0.7078953","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6081384$4259F59A-95AA-41F6-BDCB-E0472D09160A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c367d112b95646de97e8bc0b983123cb5c4dd800","datavalue":{"value":{"entity-type":"item","numeric-id":582100,"id":"Q582100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74f75e0f1ca1da4024ac3bd2ab164297d4d41d30","datavalue":{"value":{"amount":"+0.69433933","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6081384$1B89174E-3C52-4026-9982-64EAD4DF6C47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7291490d4bd37de1e51c490ce441666efdb0091d","datavalue":{"value":{"entity-type":"item","numeric-id":2416496,"id":"Q2416496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e093e4b19b975d5f5e3b9a0a3b3e9172c51d0d4a","datavalue":{"value":{"amount":"+0.6939088","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6081384$C92094E8-953E-4803-8F49-629083399B50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1112f8d8129d79ca5f9b9a2641860d2442acec9","datavalue":{"value":{"entity-type":"item","numeric-id":1044991,"id":"Q1044991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f26b737aa7416c6473f01fd377b52032497cb6c6","datavalue":{"value":{"amount":"+0.6906476","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6081384$6E9107A4-2E02-4371-821B-B34667A214DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35b0a3ba3c7b559d1e314d1421417d3a2e2d7027","datavalue":{"value":{"entity-type":"item","numeric-id":2757323,"id":"Q2757323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5327d0b610eb77edeed0b110e7879e7a51ca3ba","datavalue":{"value":{"amount":"+0.68918884","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6081384$76ABD1F9-D099-41FA-8CC8-CA81073FC913","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6081384","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6081384"}}}}}