{"entities":{"Q2088176":{"pageid":2098918,"ns":120,"title":"Item:Q2088176","lastrevid":71307708,"modified":"2026-04-13T21:21:46Z","type":"item","id":"Q2088176","labels":{"en":{"language":"en","value":"Lights Out on graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7605460"}},"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":"Q2088176$A202BC5F-9F3B-4DCF-BD9D-29CA5B5E30DF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8ccc6417274129f1c8b8fbd0503c54a9e9d2ed39","datavalue":{"value":{"text":"Lights Out on graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2088176$A7BF2FD8-BAAE-41A0-B224-B577C8FF490E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f32d1dbae27e17ea0bd4740678f26fd52e477d55","datavalue":{"value":"1502.05162","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2088176$3D9C95D5-DDB9-46A0-9AF0-5C4A4C4E6237","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2088176$9DC3E853-4A6A-498A-884C-7D92037713D9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c90c6880477e5b8205fc27abd99e34ccb378ae6f","datavalue":{"value":{"entity-type":"item","numeric-id":194541,"id":"Q194541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2088176$6CDB74DE-1F01-4694-9C31-0762B8096EEC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6bbfac5311bbcc7afa64741a2aeb20bf81782ee9","datavalue":{"value":{"time":"+2022-10-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2088176$273CBF97-6052-43B6-8189-EB1F26EAE165","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9233cab4ddd2632a1423a566b0da2adee89a346d","datavalue":{"value":"https://arxiv.org/abs/1903.06942","type":"string"},"datatype":"url"},"type":"statement","id":"Q2088176$F6F46FEA-71F4-4D95-9977-778E18120D94","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0a5f15e6fddda59a39e3cb74b762ab230fd74801","datavalue":{"value":"The authors in this paper provide several variants to the classical ``lights out problems'' which seek on a \\(5\\times 5\\) grid of lights where they also function as switches concurrently. Here touching a light will toggle the state of this light and its adjacent neighbors between off and on. So when a random set of lights are on, then the aim is to turn all lights off, if possible with a minimum number of operations. That is, a given initial state has to be transformed into a prescribed final state. Relying on a version of the Fredholm alternative, the authors introduce a separating invariant of the game and several of its variants, that is when an initial state can be transformed into a final state if and only if the values of the invariant of both states agree. They propose several variants of it, where the analysis relies on systems of linear equations over the ring \\(\\mathbb{Z}_n\\). Although it is easy to find a concrete solution to the Lights Out problem, they show that it is NP-hard to find a minimal solution.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2088176$7934B428-A902-4AD1-8222-8F7D476A02AA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c754ec9fae75fbeaa94e089f2452dc68e1235b5c","datavalue":{"value":{"entity-type":"item","numeric-id":198726,"id":"Q198726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2088176$8F28675E-D639-470D-9FAB-E97160F92862","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1be7cda1f2fda1d13448035bf1c8e3fcef0c4ff8","datavalue":{"value":"05C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2088176$07D1F622-ADD8-4586-9F66-D64088A3A6A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"822dbc4c091d9d354470bf66dcd7d659b1bcc45b","datavalue":{"value":"15A99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2088176$B1C57EF3-3DBA-4D5A-89B0-E4B23A0C4E23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bbe2dde55566c57c31463992aac9b72d0f8c104e","datavalue":{"value":"15B33","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2088176$88D25155-17DC-44D8-9095-48FC9009EB23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2088176$FDA96501-14AD-4E93-BEB9-E2DD84F3467B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2088176$539478F6-13E7-4758-94E6-50F9B0672673","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a88546c1f731ba6d392ac94f649acb68195c4e0d","datavalue":{"value":"7605460","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2088176$CDBDC542-A88F-4A73-971C-4545B27883AE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2400669b48576b6bfc8ea5b18764b701783d4f3c","datavalue":{"value":"Lights Out game","type":"string"},"datatype":"string"},"type":"statement","id":"Q2088176$24877AF7-5EBD-4E69-8485-767DC04D5043","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b2265872423bdd9540bed3782c7ded8e5d8bb726","datavalue":{"value":"Fredholm alternative","type":"string"},"datatype":"string"},"type":"statement","id":"Q2088176$3AF177A1-E396-4CDF-A93D-075EEFE4B73E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8927906f4949eb235bac26aaf035a3ce973f633","datavalue":{"value":"separating invariant","type":"string"},"datatype":"string"},"type":"statement","id":"Q2088176$802E0D25-2F4A-4D04-8E25-495E0AF3388B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99974e488eefe65e9a359b970a995a9b6d33d8e8","datavalue":{"value":"NP-hard problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q2088176$2412EB31-1E58-4BF6-8861-EB942A051327","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":"Q2088176$43774033-EBDD-4933-B126-CD17B3A9F1BB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3c08170977f224987ef4d255e23448c486b6a2f3","datavalue":{"value":"W3153862437","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2088176$D2F5E804-F0C0-4A80-8B9A-8189CE7EE8BA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c46e7a28de7799e4d7e1ce2621652ea8a123b90b","datavalue":{"value":{"entity-type":"item","numeric-id":1624858,"id":"Q1624858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2088176$C7896F39-DBAA-4B76-890D-6AFF12C9CDEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fd51bb7cd3bc633372c4f49a4370168a3b3a5d2","datavalue":{"value":{"entity-type":"item","numeric-id":672754,"id":"Q672754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2088176$AE2623BD-39D6-4604-9628-D95ADF961B86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca29d7d10d8f4dc9ce98d5874bd788d477fa9729","datavalue":{"value":{"entity-type":"item","numeric-id":4156300,"id":"Q4156300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2088176$5F9062E8-07E9-43C7-96F6-AA58A192AB17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac0822059387e360c641ce768e0d57906fd01889","datavalue":{"value":{"entity-type":"item","numeric-id":4882977,"id":"Q4882977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2088176$6D0D1A13-6E5F-48CE-A408-47E0BE0AD46E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cf0549f9117f0df9e02d37297cebcc3db3cc769","datavalue":{"value":{"entity-type":"item","numeric-id":2768402,"id":"Q2768402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2088176$54DBEA86-3D6F-468A-8100-290C381EF004","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ef0508ecea77814807889f9e63cb3c2c2c3479a","datavalue":{"value":{"entity-type":"item","numeric-id":2848975,"id":"Q2848975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2088176$B40936B8-2AFA-47D1-A7AC-FE5C72AFC961","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bec247e69995ae57feb64c50c00cb6de0f9b979","datavalue":{"value":{"entity-type":"item","numeric-id":2931489,"id":"Q2931489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2088176$DB527E08-A108-4CAF-84CF-07C2F59E78BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b6607b1d85c0cca904f36aa920bd2a1efad2796","datavalue":{"value":{"entity-type":"item","numeric-id":4393318,"id":"Q4393318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2088176$268316EE-4C60-4794-A5E6-D48E6BF74AE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e03275a96bbdd853af23ed690073ca7aa4231224","datavalue":{"value":{"entity-type":"item","numeric-id":4376554,"id":"Q4376554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2088176$09C5B542-E6C2-4CA2-B7ED-F1159E36486B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c2a66a72e9724b6448d2fd9456a13cf085088d0","datavalue":{"value":{"entity-type":"item","numeric-id":1606030,"id":"Q1606030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2088176$EFA2A6B4-ADDE-4CEC-8AF4-41B958C632C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ae74088649fa8be0b098e0bcef9769c52a5ff69","datavalue":{"value":{"entity-type":"item","numeric-id":3624970,"id":"Q3624970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2088176$65DFF289-6F75-452C-B6E5-765D9023F275","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77c8544ee72c293c5e7cf4b0f880826129178e89","datavalue":{"value":{"entity-type":"item","numeric-id":3654469,"id":"Q3654469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2088176$0600A290-B2AC-4C0C-980A-914FEC42D58F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c0789833869ce37ab1cd20af710576777f0f8dd","datavalue":{"value":{"entity-type":"item","numeric-id":1426455,"id":"Q1426455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2088176$FF3404A4-19FC-41D1-B75E-8175177C410A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d5b2450dc06e5cfe81ab4e6ce42f40bf16d0017","datavalue":{"value":{"entity-type":"item","numeric-id":4575440,"id":"Q4575440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2088176$E4C3EE25-719A-4D90-8982-2B4D28AEA333","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd11ead916f7b6f5b53251f93c97f373d76621ee","datavalue":{"value":{"entity-type":"item","numeric-id":4568211,"id":"Q4568211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2088176$96D57C9D-DB8C-4D2C-A26A-6BB046B69F35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aef3c8e7179a082678f84e44c391518e60668f25","datavalue":{"value":{"entity-type":"item","numeric-id":4600998,"id":"Q4600998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2088176$3AEA1FFA-2450-46D0-B9D8-72206E99D7D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04bcab04655d61e69ce656017c3881937859a9fc","datavalue":{"value":{"entity-type":"item","numeric-id":4242009,"id":"Q4242009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2088176$9991D73F-D78A-43B5-BB1B-F10417BE3108","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe92f044b290cbdb183578095d6feb108dbf3170","datavalue":{"value":{"entity-type":"item","numeric-id":1812609,"id":"Q1812609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2088176$22834970-810F-4B30-97CE-AB89390F2E24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed698cfb9684df195b29392d25f29caf593557d3","datavalue":{"value":{"entity-type":"item","numeric-id":4713058,"id":"Q4713058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2088176$91C85B7A-866B-40C1-B3D0-881FB5B95CEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78dc3c6af04e67fcad320e88187d9cc4496d42d4","datavalue":{"value":{"entity-type":"item","numeric-id":4392377,"id":"Q4392377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2088176$8BB1B535-03A1-444F-A0E4-A18B438C0548","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fb7e3d55bc1b08c10af4b5168a37c39ecd1ec244","datavalue":{"value":"10.1007/S00591-021-00297-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2088176$196A57E8-4EF3-4F46-9373-AF7D8EFB72AE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25b35b61d695cbae9833336738033f955c2e1338","datavalue":{"value":{"entity-type":"item","numeric-id":2848975,"id":"Q2848975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64d838285899dfc65821c1735ecee1afd445c3ca","datavalue":{"value":{"amount":"+0.8980485200881958","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":"Q2088176$BE8EC041-437A-4D64-9C1A-673A83403BEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"822ac1cfd8134997fb67e8160826acbe4b9dbdea","datavalue":{"value":{"entity-type":"item","numeric-id":4575440,"id":"Q4575440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dda2789eb8125104b72436ad3bb08c9f3c21a49f","datavalue":{"value":{"amount":"+0.869863748550415","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":"Q2088176$0B4098D4-84BE-4C72-AA26-8ADC044DC200","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e8ac3e3906be24d8a33cae10c49b24b4624419b","datavalue":{"value":{"entity-type":"item","numeric-id":992526,"id":"Q992526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f99efbbfc76d22db6e33587d3ed023919ece823","datavalue":{"value":{"amount":"+0.8550425171852112","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":"Q2088176$7941DC5C-8CBC-4CE9-82B1-567ED74305EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f1b5ad0741f15f762d239249736b305d6cfa7d1f","datavalue":{"value":{"entity-type":"item","numeric-id":5003342,"id":"Q5003342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d7df93a3c54e2a4800988004af445ad0e2c84c2","datavalue":{"value":{"amount":"+0.8298788070678711","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":"Q2088176$48827274-23E9-49E6-A222-32CF1F253BC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1bab15945447d0ff57f599e5ae78c362fadb2157","datavalue":{"value":{"entity-type":"item","numeric-id":1624858,"id":"Q1624858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d765310c0a17f3e0c514949893bfe78b3c53593","datavalue":{"value":{"amount":"+0.8256917595863342","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":"Q2088176$C314EF99-8FC5-4D45-A819-DF606BBBBC5A","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2088176$9CEDE20D-5AB2-485B-83AE-FFE4A224BA27","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Lights Out on graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Lights_Out_on_graphs"}}}}}