{"entities":{"Q1010920":{"pageid":1012768,"ns":120,"title":"Item:Q1010920","lastrevid":66004629,"modified":"2026-04-12T06:53:07Z","type":"item","id":"Q1010920","labels":{"en":{"language":"en","value":"The complexity of constructing gerechte designs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5541080"}},"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":"Q1010920$42B71BDE-7952-4089-9AD2-1039166A032F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"34a471a601ae6808cf2581a7f7a08c840db1b5e5","datavalue":{"value":{"text":"The complexity of constructing gerechte designs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1010920$9A6A7B74-E2A0-43D3-96AC-10DB72E871AA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2b4ab0cffa5a90c67f476a5b0383ee0c9371a459","datavalue":{"value":"1159.05010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010920$9AD97DE3-2F4F-4D5E-B28C-19ECFDDB5029","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010920$B330BE38-1EB4-4D1E-AADC-2178A93885BD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f584a175cfc2fafdfc362244f176e06010bbf381","datavalue":{"value":{"time":"+2009-04-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1010920$E97D9050-6975-47C5-BA8A-05BA46CA3609","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5d47cdfd12bafb6a17857429f5fc477447a8d3de","datavalue":{"value":"https://eudml.org/doc/129753","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010920$58A66FAC-FBBF-4092-A300-691DB99C5BE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"3bde0308b42203bd2fa78176b304d60c16cc210a","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1r15.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010920$7C5D4D10-ECA9-4E69-B86D-59063F531DA1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"053a901306c5045d5783c9eeeaf4ec68b8b758eb","datavalue":{"value":"Summary: Gerechte designs are a specialisation of latin squares. A gerechte design is an \\(n\\times n\\) array containing the symbols \\(\\{1,\\dots,n\\}\\), together with a partition of the cells of the array into \\(n\\) regions of \\(n\\) cells each. The entries in the cells are required to be such that each row, column and region contains each symbol exactly once. We show that the problem of deciding if a gerechte design exists for a given partition of the cells is NP-complete. It follows that there is no polynomial time algorithm for finding gerechte designs with specified partitions unless P=NP.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010920$B3D54C04-923C-4734-8580-D3DB056697DE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0fb5c2b5135b23a64eead86c75bb584d8442d720","datavalue":{"value":"05B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010920$9C1F19E4-EBD5-48A0-AE3A-530CF6227A84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010920$16D1D83E-6FF7-4D88-939A-3AAD15120E9F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"59b22a8f5dbcc004fb48f44d439cf22b0392c4ee","datavalue":{"value":"5541080","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010920$9040CE6A-7CB7-4176-8E56-257933BC5BF7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"871669c4df9f7d06b3f76767c2e6f09a5dbc9d41","datavalue":{"value":"grechte designs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010920$330E586D-938E-4B7C-82CB-B4394BBD6EEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bff73f095c4d4803c41cae6118df4d06014758cb","datavalue":{"value":"latin squares","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010920$6D615F1A-CCDC-4D64-B733-3F2A0E87CEBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"405db27291ed1c7f1a3598a731124778bca338e6","datavalue":{"value":"partition of the cells of array","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010920$D6353F5D-4FFD-498A-985D-0B7B50B87918","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"61b5d1ab2a5f00cfa0c238c08f01100fbe4c0e45","datavalue":{"value":{"entity-type":"item","numeric-id":456380,"id":"Q456380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010920$4B30AD20-3E50-46A2-982F-02875622DD0D","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":"Q1010920$9E5CCA41-8442-4C94-BCC7-25688303982A","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"33dceb6109bee974e1561d6110dbbebc9f01d717","datavalue":{"value":"bafkreihf76rb3tcwqeq7hrs76i5e542x5kzbvgbuf3uhtm75necjuerxxi","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010920$7E975856-676D-4E1D-A7AA-5EC8C9E40BDB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f893de7779313ef47531cb2d79d6e21c8c72222d","datavalue":{"value":{"entity-type":"item","numeric-id":3165562,"id":"Q3165562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"799a19f46793b69941bd20fc3e1f68c353398a47","datavalue":{"value":{"amount":"+0.8235881328582764","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":"Q1010920$F64C61BD-38DC-456C-B20F-E5BB5AD2CEDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ffbb3a3801b1fedac308d512eba2ff33daf8824","datavalue":{"value":{"entity-type":"item","numeric-id":5951961,"id":"Q5951961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd2c0abf4274b67d80a831a775594dad278a5f04","datavalue":{"value":{"amount":"+0.7621862888336182","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":"Q1010920$2F4DA870-17D0-460D-9801-F197479AE186","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"118a53adab81daa44602c43c7e376b059bf1fef8","datavalue":{"value":{"entity-type":"item","numeric-id":254879,"id":"Q254879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91c8ea8eb4d2b70475d0026ec31b0b5300eb8ae8","datavalue":{"value":{"amount":"+0.7593919634819031","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":"Q1010920$06859A4A-DA56-4FDF-97CA-6463657AF66F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c38f5ccfc92188f92ecce465572ef8ebcb14bca1","datavalue":{"value":{"entity-type":"item","numeric-id":793029,"id":"Q793029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c1996065bb7589024bc7e63708e7858bb0f4d60","datavalue":{"value":{"amount":"+0.7569471001625061","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":"Q1010920$851F71AA-A985-482B-8FCA-F87A555FA1AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf8f95704253ae168737750df471715a1e18b2ef","datavalue":{"value":{"entity-type":"item","numeric-id":3340871,"id":"Q3340871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d473fc27061259ae4dea313bc7af6818784e07e","datavalue":{"value":{"amount":"+0.7387182712554932","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":"Q1010920$29F1B390-6CE8-4AE9-96BF-95EC4000E84F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The complexity of constructing gerechte designs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_complexity_of_constructing_gerechte_designs"}}}}}