{"entities":{"Q1090274":{"pageid":1101026,"ns":120,"title":"Item:Q1090274","lastrevid":66907653,"modified":"2026-04-12T13:39:46Z","type":"item","id":"Q1090274","labels":{"en":{"language":"en","value":"PSPACE-Hardness of some combinatorial games"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4006037"}},"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":"Q1090274$F953BA10-8A38-4172-9410-B86219600989","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"433ec6be7a2ed69feed4d13e2a1e5b26a00852f8","datavalue":{"value":{"text":"PSPACE-Hardness of some combinatorial games","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1090274$3889F5D3-6481-40EC-BACD-43EF67353F63","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0f1e00195bf4d372e9d4fe3d626ca72de932d72e","datavalue":{"value":"0619.90109","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090274$70DEE6CB-21AE-40D6-92D8-74E2EB42CE6F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"db74f21244d72df9dc27eebf957903d614153b76","datavalue":{"value":"10.1016/0097-3165(87)90074-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090274$15DE2F54-A63D-4721-9F23-9AF78C7169B7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6e709fecaf3540b3e05639431386acc098a31770","datavalue":{"value":{"entity-type":"item","numeric-id":200918,"id":"Q200918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090274$5464FB25-D5DF-4699-B95A-A89979DB51AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bd217505f392c707ef78912fb29990d0551df4c1","datavalue":{"value":{"entity-type":"item","numeric-id":1090273,"id":"Q1090273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090274$B6BBFFF3-6283-4560-852E-E544CDDC6213","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1c03f12d2ae232c6413ffedcffaa255461d32f1a","datavalue":{"value":{"entity-type":"item","numeric-id":171729,"id":"Q171729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090274$182E087D-5996-46C8-80AB-A5EE2C2781EF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1090274$340A7725-E61D-4207-A1F9-476DA8125FA9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ad780b50dbe29a76bed9cfe14f6c08d70e79d179","datavalue":{"value":"PSPACE-hardness of four families of win-lose-draw games played on a digraph with blocking, capture, or annihilation rules is proved. Special cases of three of the families are shown to be PSPACE-complete. Further, the PSPACE-completeness of six families of win-lose games in which two players mark or remove nodes of digraphs according to given rules is proved. The first two families contain partizan games, the last eight impartial games. All the games have been defined previously in the literature or are slight variations of such games.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090274$687A095C-91A3-47B2-8F5B-E9F1AA7BB2BC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5fbd0918ba2c4a1aeddd30d9d3d146d9773f1239","datavalue":{"value":"91A24","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090274$2D7B7B3E-14A3-4271-8941-5224F81A4A8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090274$C03BEDE2-0389-4F9D-8561-5547228DE8AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090274$4C629906-8070-48D8-BF8B-8071E74EA3BC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b9976010d23f871a055d04f703dd41b6704a4cf4","datavalue":{"value":"4006037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090274$4A006180-5699-4518-8AC2-3AC2B9F7190A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59b372c983c0c137e6de916577c79a8e975d0fd4","datavalue":{"value":"games on digraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090274$E8BA0F4A-7D45-4689-BE53-5CE5D6B8A3BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"535d360cb8c0c1aa80f78a968709bdfad17bee58","datavalue":{"value":"combinatorial games","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090274$3F79C13E-74BE-4DD7-ACA5-2A2C06CD1653","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"16284ece4670b3d7275c2ce344fa55e4a47741a5","datavalue":{"value":"PSPACE-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090274$843D8AA1-BDF6-4BC8-BA2E-6282A350FF00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2054408cf6d1c083c91e445ae258d7b05b2a8abe","datavalue":{"value":"blocking, capture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090274$2F315B3C-6542-4F51-ADF4-14A20E6899C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f9cb7aa7ea6916043d50c81c293b412588e488b","datavalue":{"value":"annihilation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090274$4B36EAC6-EA53-4ADC-85E8-C4FFE9510C01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"09b7528120ef50a8f5205cf42893c121e1d21b40","datavalue":{"value":"PSPACE-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090274$6F3FC123-96EB-4232-91C2-A05BD8B8A4E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b869d8da8146677a3d40bffa92d1e0d9598b9667","datavalue":{"value":"partizan games","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090274$9961F34C-B3CE-4F25-868A-A41B2B1788EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a7a91a4c0c897d065a4103affe35165afa722379","datavalue":{"value":"impartial games","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090274$518D8484-9051-4227-842A-9BCC3D8EE93A","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":"Q1090274$1C58D86A-C4F9-44C9-8E6C-33FA14308783","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"19e897a4cf025063602744b2008ff2cf8f125a68","datavalue":{"value":"https://doi.org/10.1016/0097-3165(87)90074-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1090274$880E1B2D-9D6B-475A-B786-E05ABF711F09","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0ab0f74459558bdea247178a9ca58fefcfb3e1c0","datavalue":{"value":"W2077313418","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090274$0AC79BE7-8B46-4D8C-9E5F-6B0F8B2D9ABA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"728964734428e8655cb87cece2fff202f92850f3","datavalue":{"value":{"entity-type":"item","numeric-id":3944542,"id":"Q3944542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090274$18387E91-C4E2-4E0B-86BC-603218448CB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ab3bdd7d7fbfac1006a4b16e8a3687950389993","datavalue":{"value":{"entity-type":"item","numeric-id":4099541,"id":"Q4099541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090274$0D630EA8-CAA1-4605-95EF-3EBE4B348121","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46b6d70cfd3ba4ec276ffb558fe15410d7040457","datavalue":{"value":{"entity-type":"item","numeric-id":4127387,"id":"Q4127387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090274$75FF3933-C298-4076-8F9F-79E1E37CE6AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2faccc88ec30ea9571262d8333e96215c55bd373","datavalue":{"value":{"entity-type":"item","numeric-id":1137948,"id":"Q1137948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090274$C022BDCD-0755-4B93-A897-BC90D9CAA8B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7f7f68fcb5350b7f905df9838fc3f5e766137c4","datavalue":{"value":{"entity-type":"item","numeric-id":1168901,"id":"Q1168901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090274$0FC7ED71-4E70-4F5B-8D6A-094BA7AC31A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08e4246929a22c20e2e31c3fc16bea566141c26e","datavalue":{"value":{"entity-type":"item","numeric-id":3873542,"id":"Q3873542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090274$CA2AD60E-FBD9-41E0-AA9A-E6CEBECFD56F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b773ee5b291ebab239e6e8e7787b49c4d2b3c4cd","datavalue":{"value":{"entity-type":"item","numeric-id":1248466,"id":"Q1248466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090274$6FD7F8E8-0EF5-493D-8F5C-ED869C5EA26A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f33f843778dfabfeef453cdfa627d4b42c24908","datavalue":{"value":{"entity-type":"item","numeric-id":4131648,"id":"Q4131648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090274$0EAE5671-920C-4234-87F5-FDC7E15BC518","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29f34bf593dc45150d91df3a11721d9508b75f4f","datavalue":{"value":{"entity-type":"item","numeric-id":1139510,"id":"Q1139510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090274$0562ACB6-D2A3-45B8-8479-C10AFED5ED48","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08e3919a424f440c03a5fff35e6bd8e2a0e7f47b","datavalue":{"value":{"entity-type":"item","numeric-id":2127615,"id":"Q2127615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ea2959a6c96f99a1f7cb9359b0de38de8cbb747","datavalue":{"value":{"amount":"+0.8207188844680786","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":"Q1090274$80EFECF2-F546-420A-9CA0-714047A5D477","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a99ae1c36c543f00bae1753bbb08198889a36e7","datavalue":{"value":{"entity-type":"item","numeric-id":4407697,"id":"Q4407697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb6d2f598a3493b4f2fca23c6316579bd0bfaa28","datavalue":{"value":{"amount":"+0.8097885847091675","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":"Q1090274$FF913013-1229-4374-BE6B-6E92CE135E00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef6fb5e65332aa7c6cd1a81775f4885e5cd6457b","datavalue":{"value":{"entity-type":"item","numeric-id":3295616,"id":"Q3295616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"584d7294d4dc371fe6360bee39f35953c37aedfb","datavalue":{"value":{"amount":"+0.8041655421257019","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":"Q1090274$C3C51F1A-9DD0-4B0A-8871-78DB7A8F0648","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":"10bc51e179ed7c0ed84c513c9081b60303a78e05","datavalue":{"value":{"amount":"+0.8014446496963501","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":"Q1090274$FD8405B7-7690-4D44-AC09-63F708A5BC0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c1c787a01130190722bc3ef22b2d8a403cea711","datavalue":{"value":{"entity-type":"item","numeric-id":2002060,"id":"Q2002060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e0e0796815db2e083a6bd0632291c33ce305ec6","datavalue":{"value":{"amount":"+0.7987595796585083","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":"Q1090274$512B55F5-680A-4AB1-A600-7946BE41E983","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"PSPACE-Hardness of some combinatorial games","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/PSPACE-Hardness_of_some_combinatorial_games"}}}}}