{"entities":{"Q793029":{"pageid":794877,"ns":120,"title":"Item:Q793029","lastrevid":42698281,"modified":"2025-07-08T14:31:13Z","type":"item","id":"Q793029","labels":{"en":{"language":"en","value":"The complexity of completing partial Latin squares"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3855122"}},"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":"Q793029$E1EA167C-DD0C-41D9-93EE-B10627FE646F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b92b2986bd44f7023ea38fbb0928be8b3a96f0d9","datavalue":{"value":{"text":"The complexity of completing partial Latin squares","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q793029$28CAD0CC-3269-4F48-B99B-36F9FE6836C0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4b16fbb5684cc2c4e62e7c296bde9f831f1dfddb","datavalue":{"value":"0538.05013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793029$0DE684DB-9FD5-4BE1-8EB8-D744C3697C17","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"259da3f7ea84f0c0afcb263bc7c014370b7d782d","datavalue":{"value":"10.1016/0166-218X(84)90075-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793029$DDFACB8B-364F-4D49-92D5-322C05B0C0B2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bbbdc3381c094a1abe2cf60ed445a4984b25837b","datavalue":{"value":{"entity-type":"item","numeric-id":168193,"id":"Q168193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793029$48F46036-839C-45AD-87A9-839F55B92A29","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793029$068D7C35-9B6B-4B07-81F3-7CC0C6FF59D8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q793029$8067E4EF-03E4-4A26-9AAD-2A592F50A135","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"32df6763af19a8624d79577c1fe26654c119cc0b","datavalue":{"value":"With the aid of a result of \\textit{I. Holyer} [see SIAM J. Comput. 10, 713- 717 (1981; Zbl 0468.68069)] the author was able to prove that completing partial Latin squares is NP-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q793029$97B22515-3A7E-4C49-9244-15D9D7529334","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0fb5c2b5135b23a64eead86c75bb584d8442d720","datavalue":{"value":"05B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793029$EC09E7F3-8311-4FD5-9FB1-3C9FA22126F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793029$6AB670EC-4584-4545-AF5C-D39A45337EF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793029$2E399204-262A-4EF6-AE24-018A675877E6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d637b7bef468ddc5a9f6dd86da53d32ec210a742","datavalue":{"value":"3855122","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793029$A4945E32-1AC1-4530-B969-A17D43B2C96E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"23ec6145e3ae3651ee52ad3aa352b7a02c29d62d","datavalue":{"value":"partial Latin squares","type":"string"},"datatype":"string"},"type":"statement","id":"Q793029$4EC29550-160F-47F0-A1E5-D10C969C278A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"07edf0834856fb6170b70e6b632242186b521322","datavalue":{"value":"partitioning tripartite graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q793029$7386CCC4-CB74-4F3A-99C1-DB8CF34D494B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q793029$692136A6-D358-407B-9A35-4DC5BD673AD8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d9e169a1c580dd2beaca5b190c93d5ea480a7ce1","datavalue":{"value":{"entity-type":"item","numeric-id":588122,"id":"Q588122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793029$10FD840D-00E2-4EF0-A992-AAF00FEC796B","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":"Q793029$2E0DAE44-D48A-4058-BF5C-5609C7A15927","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"f88530256878b0cc44d426af894189ba79fed874","datavalue":{"value":"Q55880491","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793029$82BD6D55-15FB-4F3B-8311-71CA75573078","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793029$C4960C96-B13C-4325-9F3B-856D1E333A6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96b5f1a9f3826707511e542fe01cc3e5593afa39","datavalue":{"value":{"entity-type":"item","numeric-id":787671,"id":"Q787671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793029$8D4E353C-202F-41A3-BD11-E203A0A8F6BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fcdb5f9f574e74a44fc1a8671dbbc54ec3f902c4","datavalue":{"value":{"entity-type":"item","numeric-id":3972909,"id":"Q3972909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793029$B6A14A17-F0AA-4F64-8BB7-E53A8536C4B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a1e0be834341e67496e26f97981dcd5f097a920","datavalue":{"value":{"entity-type":"item","numeric-id":4186334,"id":"Q4186334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793029$92D196AB-C7AB-4D3D-9013-8EC48EF9A8C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"156e0039392d6ef79c6665c628ac60551f79308f","datavalue":{"value":{"entity-type":"item","numeric-id":5790243,"id":"Q5790243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793029$C1D51483-4F0A-4B80-AE11-59C7A631C853","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4534d792f5262a1f297a74f9b43efedcc5cd94ec","datavalue":{"value":{"entity-type":"item","numeric-id":4760022,"id":"Q4760022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793029$088BDD2F-57FB-435E-B409-EC9A02D8EB44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8eb3c782134072d590e01e5c057dd2ac2114eeb","datavalue":{"value":{"entity-type":"item","numeric-id":3233211,"id":"Q3233211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793029$C7AA6704-166D-4703-959E-94D9BAD3D43A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff5e201c2b579b8c70d76c6408c175e8ca744357","datavalue":{"value":{"entity-type":"item","numeric-id":3922182,"id":"Q3922182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793029$14A730BC-FDE8-4C46-B2EE-2779781B7E84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"187e1fb158e6b4695b1eefc466a8e0535eaf95e7","datavalue":{"value":{"entity-type":"item","numeric-id":5682014,"id":"Q5682014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793029$50FE141A-4452-4B3F-9F65-E666DF3CF25B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ec4b0a06902f20c06116057e745c5eac0e0da11","datavalue":{"value":{"entity-type":"item","numeric-id":4137190,"id":"Q4137190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793029$2DE4D912-6528-4CF1-BEB2-D8E371017710","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5af0088492ba74f77fca3fe0b9bbb3ba29d67808","datavalue":{"value":{"entity-type":"item","numeric-id":5627526,"id":"Q5627526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793029$401B9AC4-39D7-4D09-A35D-70CBAB905A93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b088a5e2d7e73c233a78e7c077590beb3eed202","datavalue":{"value":{"entity-type":"item","numeric-id":5805003,"id":"Q5805003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793029$2EBE8278-4A6C-45B6-9AE6-09CF5AFB49A4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"63ff9f92d991b69141f95846a0fc13234fc9a5f8","datavalue":{"value":"https://doi.org/10.1016/0166-218x(84)90075-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q793029$72DC8486-7B7F-4EE4-9DD9-14874CDAD57B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"54285e5e324dadf289da5dc1f62198455f71fbcd","datavalue":{"value":"W2083140445","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793029$0D5FDAFF-BC05-42A4-9B12-5EF47D6FAF53","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8100e8891d6c7654bac75dce9cbc46e4a644c54","datavalue":{"value":{"entity-type":"item","numeric-id":4526643,"id":"Q4526643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73539c930dcc57f4319a7796a14caf1f6095b24d","datavalue":{"value":{"amount":"+0.9529261","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q793029$22C4B93B-92AE-4486-9A04-E0DC737749EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91daa6ef7fe04c758213565dcd28ddae026129de","datavalue":{"value":{"entity-type":"item","numeric-id":966163,"id":"Q966163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0866598805f2be01cf3c8b59b3d364ad6bd6be48","datavalue":{"value":{"amount":"+0.9343209","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q793029$D5C84378-8DC9-431A-A4E7-EB291D7A64F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"849e40fad898d288247d57e246a6f83f9f797710","datavalue":{"value":{"entity-type":"item","numeric-id":4677898,"id":"Q4677898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f4e0245d9d2adb566825341bfca4b70b858a6ac","datavalue":{"value":{"amount":"+0.92916095","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q793029$8B6CCABF-DC3B-4003-99E8-0B6CAA1433A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc2b77d102a55d6388ccf1f9e1dd1a3aa3bca008","datavalue":{"value":{"entity-type":"item","numeric-id":3222205,"id":"Q3222205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed6776818b327fc06800385af9f630ded4033984","datavalue":{"value":{"amount":"+0.92116004","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q793029$13313B11-C5B7-48B1-9DA9-2BCCFC921289","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c95a3974768da03f50c16cdf66db7546be7ca56a","datavalue":{"value":{"entity-type":"item","numeric-id":409474,"id":"Q409474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"201ef8023b2eaf1e4ba6c5ef6c6d4880a0e98741","datavalue":{"value":{"amount":"+0.9202689","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q793029$BF69EE52-0557-4275-B5D7-B528F0329246","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f70c4224166eacf7e9e2155c06f7f42242e37239","datavalue":{"value":{"entity-type":"item","numeric-id":2864800,"id":"Q2864800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89a1264ce6c1b8c2eff6eb94cbe69991263b3795","datavalue":{"value":{"amount":"+0.9068159","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q793029$C5C6211B-DF7E-4700-B8A4-14CFE67AA1DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2979ef1fe3107088d57b39feed85af4a8250cfc2","datavalue":{"value":{"entity-type":"item","numeric-id":4677944,"id":"Q4677944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95cd2def7bdc1350aacad3ab2cca1460a50863b3","datavalue":{"value":{"amount":"+0.903499","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q793029$3DE40A33-2935-474D-87B9-F0C826BB3C34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4aed1260a6e4d6b88f4a58a4bdcbd59355202529","datavalue":{"value":{"entity-type":"item","numeric-id":3590962,"id":"Q3590962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"124bc6f5ba98a48edf031c1989fc6a234942c0a0","datavalue":{"value":{"amount":"+0.8999592","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q793029$D084C873-8596-41E6-B4D6-F643958317CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d06394c0212919d8799e28f466a40426524a2ed6","datavalue":{"value":{"entity-type":"item","numeric-id":4514224,"id":"Q4514224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"329d8d9fc24ea2af43dd9ee401109ca621472ce6","datavalue":{"value":{"amount":"+0.899959","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q793029$ED0186AD-8168-4CC2-8DBB-D1736A1218B6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:793029","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:793029"}}}}}