{"entities":{"Q6150678":{"pageid":13284985,"ns":120,"title":"Item:Q6150678","lastrevid":102432620,"modified":"2026-06-06T04:26:51Z","type":"item","id":"Q6150678","labels":{"en":{"language":"en","value":"Deciding whether four perfect matchings can cover the edges of a snark is NP-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7802229"}},"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":"Q6150678$EC7F5F6F-B3E0-4560-B3B5-C55B7A928B39","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c9962cab4ac4f28122e7e552f28ab196d5d62a98","datavalue":{"value":{"text":"Deciding whether four perfect matchings can cover the edges of a snark is NP-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6150678$AFF3D0D0-24D1-4FB8-89F3-F8849BF813A6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f0ecf801fd2819af52bd1f069937d6e562769bd7","datavalue":{"value":{"entity-type":"item","numeric-id":166312,"id":"Q166312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6150678$93F71668-2B13-41EA-9227-FAE925C38E98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0d5edccae9fbb3d2638ba0cc75e132fc3dae5316","datavalue":{"value":{"entity-type":"item","numeric-id":6150677,"id":"Q6150677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6150678$332ECF7F-2F4E-4E46-BD22-82FB0E3A2181","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6150678$00A4F713-D159-4AD0-8614-C87D62A09C56","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2243c5bdd19f18fa9565faa280a383f10c98f880","datavalue":{"value":{"time":"+2024-02-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6150678$462A4410-1584-41BB-AA25-A00A839262D0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f969879f531643f058f8dd4c87a7dd4eb7b8c4c8","datavalue":{"value":"68Qxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6150678$E7F34DD8-D712-41D3-8ACB-ECAC7953137B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a67752a525d0dbe0494d03ba4a698b78450d0f95","datavalue":{"value":"7802229","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6150678$224BE000-2436-4D3D-8DD2-5BCAACB854EC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e01f33e43354d516b8d6e654c1ded76a55047726","datavalue":{"value":"cubic graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6150678$98B436A9-DA68-4DE0-A327-B222DE87501F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19ec132a1ede33f50fb04fa222303f9cda249a50","datavalue":{"value":"perfect matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q6150678$C2979779-D72A-41DA-B33E-34405D6693A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e3d58b5f68ae7d6337620e7d25da0081273ed23","datavalue":{"value":"edge colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q6150678$9DAC4868-5AB7-490A-BC92-08E61752043D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9ba9cf75f745dd55cef9797a8a50252799340731","datavalue":{"value":"snark","type":"string"},"datatype":"string"},"type":"statement","id":"Q6150678$64A43196-4670-4325-A634-1253DB57EBDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q6150678$02EBE86A-5530-4FF0-9F5A-3BFE46C8E449","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":"Q6150678$F6707611-51E9-4D7D-9360-FBE9B5E933A8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"be2563ef2a4aec9f5ac8262498b5e7a75c4c65ed","datavalue":{"value":{"entity-type":"item","numeric-id":727053,"id":"Q727053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6150678$16777070-81ED-41EF-8583-EE7429E966CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f86999ba58e97e58eab736310f51a54f0daa3026","datavalue":{"value":{"entity-type":"item","numeric-id":463288,"id":"Q463288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6150678$924058E4-6965-435B-B96C-C6D447E669FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81d8a0ac67e074af2783991b082cd18a14315535","datavalue":{"value":{"entity-type":"item","numeric-id":5668263,"id":"Q5668263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6150678$4406E2BC-A955-4407-A7CF-58AF48E9851D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75aebb8ee340b2f085708f0773160a2f8953792e","datavalue":{"value":{"entity-type":"item","numeric-id":4240563,"id":"Q4240563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6150678$6113C587-5040-4A85-AA71-5C4B70F940C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631200adace0f14c2f6d92fc47cb2d9f5d82cdbb","datavalue":{"value":{"entity-type":"item","numeric-id":3928241,"id":"Q3928241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6150678$7F6F0985-C8D7-4C8C-A4CB-40BD09738EB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f81dc4ef189ac93a2b54b0ef319bf377a11c0f8b","datavalue":{"value":{"entity-type":"item","numeric-id":1924136,"id":"Q1924136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6150678$8BA7631B-E49D-4D07-AF6D-7140623C8FD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d50b6a579ac59f33a101b67249654a5bab1819c","datavalue":{"value":{"entity-type":"item","numeric-id":2519796,"id":"Q2519796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6150678$18443BF2-6330-4877-84CB-F168500C6386","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0aaefc8d0913f5251ccb0a790bf74d8f91f44a0","datavalue":{"value":{"entity-type":"item","numeric-id":2040017,"id":"Q2040017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6150678$A0B4BF72-0C8E-4DBA-876E-F696C5E7120E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c3294c5a0e61d1c833c73484e515dcbe673949f","datavalue":{"value":{"entity-type":"item","numeric-id":2225424,"id":"Q2225424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6150678$519BE111-E021-4270-B1B1-0ABF8603A8A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b64f9522f91aa12ca412d351b6970b7f3ec8d1f","datavalue":{"value":{"entity-type":"item","numeric-id":4997131,"id":"Q4997131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6150678$97A2D3AD-838D-4303-B265-FD939C0448F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9799935fa6b5975808f92cfcc703600c2e6e3c88","datavalue":{"value":{"entity-type":"item","numeric-id":2726740,"id":"Q2726740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6150678$C1CA52EF-5AF5-47FF-A4F3-12F33D41BF73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ad582fa56fae2790737242e1c9c205b63f2231a","datavalue":{"value":{"entity-type":"item","numeric-id":4756846,"id":"Q4756846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6150678$27F516E7-452B-462F-A92D-45119886A385","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e99da589d7100fee8c775ba840d0a2287dbe7cc7","datavalue":{"value":{"entity-type":"item","numeric-id":4198789,"id":"Q4198789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6150678$F159FB7C-D8B9-47A3-844B-82651FDC6B04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f350e5046afdfee02a3c280e08266212af067f39","datavalue":{"value":{"entity-type":"item","numeric-id":4982281,"id":"Q4982281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6150678$A521C11E-BBC1-4E1E-A2F6-C0D8FAF11BA2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"42b59d14e3eb774128e48788a638929298354ece","datavalue":{"value":"10.1016/J.TCS.2023.114374","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6150678$864D9F35-C410-4065-81D5-FDAAF7D5AE40","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3cf84d057a3ad4f6c27734df3e5b9d63d755ac3a","datavalue":{"value":{"entity-type":"item","numeric-id":2040017,"id":"Q2040017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2a0347bd22519829270e7c9906f82e4935882ae","datavalue":{"value":{"amount":"+0.8688302636146545","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":"Q6150678$D12CCD97-19B2-4B2F-967D-FE7AD36C9652","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bbbb83c367b44eab187c9fdb6ea859e3312c5e56","datavalue":{"value":{"entity-type":"item","numeric-id":2342641,"id":"Q2342641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a8f40e5fb50f3a5701f3185c7444942b9955c39","datavalue":{"value":{"amount":"+0.852720320224762","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":"Q6150678$2DFFEFDC-9F94-46E4-B500-B0E0F0A5876A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Deciding whether four perfect matchings can cover the edges of a snark is NP-complete","badges":[]}}}}}