{"entities":{"Q2943894":{"pageid":2954614,"ns":120,"title":"Item:Q2943894","lastrevid":58064919,"modified":"2026-04-03T16:14:04Z","type":"item","id":"Q2943894","labels":{"en":{"language":"en","value":"New NP-hardness results for 3-coloring and 2-to-1 label cover"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6478870"}},"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":"Q2943894$39D5E3FB-AC6D-44A0-BB05-EB4CE3E596A5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"55ea8c1f04fc8c0541b0c87c94a19b019edba700","datavalue":{"value":{"text":"New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2943894$5773DAF4-0D3A-4BF3-A3B4-1C24A5F5A5F4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9d259914edcc3400dda25e9ab9cf03878579defa","datavalue":{"value":"1320.68087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2943894$AF0ADB5E-860D-4F8C-BF2F-8CD7308DBC49","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1600132ffc74f2894151dadc5c3eecbd3ab73687","datavalue":{"value":"10.1145/2537800","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2943894$F9B65CDE-5B06-4A5C-9D45-EE1CDD7B8C72","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"64bbaa3c401dec878328d8d72c14b0373fd9aac2","datavalue":{"value":{"entity-type":"item","numeric-id":92716,"id":"Q92716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2943894$B89CB7AB-75FF-4A7B-AA88-F7B1D47FCAEC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e6dc6289bab1690ff13b6065c70cfdc922567dec","datavalue":{"value":{"time":"+2015-09-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":"Q2943894$67BECEFD-1691-4A15-82DD-7212EA28C379","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c5ca2a3ea7595934c103f41390ead5ad8e816e99","datavalue":{"value":"https://arxiv.org/abs/1210.5648","type":"string"},"datatype":"url"},"type":"statement","id":"Q2943894$004821F2-8B52-4201-8BE5-BA977C9F757A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2943894$328883D2-A9F8-46AD-96E0-4A69BBF4A24C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2943894$4BDC0ECA-7017-4C2F-82D2-8A4D5E419436","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2943894$D9E8FF36-F6AF-4A08-A5B0-313BE22A16B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2943894$734E13D3-DBF2-44F6-AD5B-31B01B1DE343","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4267ad51a879a6538930742712eef6f088d62aab","datavalue":{"value":"6478870","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2943894$51E7BE91-2017-46C0-87CD-4D683A73E051","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2943894$002E0396-55BD-439A-B574-BBEB9ACD2810","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"df25359605a7bacf8d12705a29fce2b79e2bb8b0","datavalue":{"value":"constraint satisfaction problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q2943894$38048A0C-E286-4D3D-8F56-1B4D2F11D234","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2943894$FCE72A67-B383-4615-8551-06948C6B3B2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"93410e6e2031fdc130d3abd416e44af23627a5b7","datavalue":{"value":"label cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q2943894$EBCC7CB2-E328-4DA5-BAA7-67D24591DBF3","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":"Q2943894$92E9708A-9766-4F6B-ACF0-18C48D730BEF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e8c1fea43c896816ef6b25e9372bf5987b738281","datavalue":{"value":"W1991265104","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2943894$B11F16AC-84A1-4A74-964D-788AB4292828","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dfab507649397c554a8e92a5571a72761344e2b8","datavalue":{"value":{"entity-type":"item","numeric-id":3177749,"id":"Q3177749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2943894$5DCDD8C7-DD00-4CB8-BB81-3F03D9819B44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d83a00e805cb41e3f8ce716054d3b105e6a3db97","datavalue":{"value":{"entity-type":"item","numeric-id":626619,"id":"Q626619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2943894$CC56AC3D-1D7B-40A8-92A7-AF6AA026377D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3a46e5386af9cf07dcd9bd88e68d205a0f035cc","datavalue":{"value":{"entity-type":"item","numeric-id":3167380,"id":"Q3167380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2943894$4C10A525-4BF6-4FC2-863D-E31DB5A9AE35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdf95036156924b6beda5c34881531201e6f9ae6","datavalue":{"value":{"entity-type":"item","numeric-id":5495026,"id":"Q5495026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2943894$27136927-3AE7-4F9F-B285-73EAF40BB88A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d944632fa28171d250995fdc2fcdede8179b805","datavalue":{"value":{"entity-type":"item","numeric-id":3575151,"id":"Q3575151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2943894$FFBE725D-F82F-46D7-A777-164A61F15853","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f503f6e8d6c9bf5f7d668edeb911a6daa4be963","datavalue":{"value":{"entity-type":"item","numeric-id":679447,"id":"Q679447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2943894$59AC7993-9073-41CD-A4DC-F18925D0684F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bed8309b2ce4a1a66af1ed0a4342239ee8b5ff21","datavalue":{"value":{"entity-type":"item","numeric-id":1887719,"id":"Q1887719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2943894$BEE3B923-D7B7-4584-8E24-98917EE6CECB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca34a9fc98debfbe5327eee8c40e7f3baf88965a","datavalue":{"value":{"entity-type":"item","numeric-id":3638876,"id":"Q3638876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2943894$42A6CF39-D420-460F-9CA1-2BBA7489BBD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a828804f3dd49e34630ac057b5e1cbbe401690b","datavalue":{"value":{"entity-type":"item","numeric-id":5495027,"id":"Q5495027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2943894$2E9EFEDE-141B-44B2-B5DA-3B1413E6285F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aba1068e97967d10529a897411edad8d5fcd96ca","datavalue":{"value":{"entity-type":"item","numeric-id":3587413,"id":"Q3587413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2943894$1DF3B17E-AB37-44FE-8605-1943AE1DA89A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63223a2b10e799e0a620d9698b0286ebd9668db5","datavalue":{"value":{"entity-type":"item","numeric-id":5441360,"id":"Q5441360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2943894$9C5B45A1-0799-414E-B913-42293E3B6F96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"112fa1e16c28072d1b690d88a68f10e9a878f19f","datavalue":{"value":{"entity-type":"item","numeric-id":5943094,"id":"Q5943094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2943894$468AD68A-4499-46A9-841E-3E436D951B76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e1a59b9106a5dd5105f2bc476300c4cdae45ec3","datavalue":{"value":{"entity-type":"item","numeric-id":3579218,"id":"Q3579218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2943894$95A98F1C-01F7-41ED-B94F-2E305F7F4C53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d573bfef7b8cc8f39c4a0ab97b094977c16fbaf6","datavalue":{"value":{"entity-type":"item","numeric-id":3579632,"id":"Q3579632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2943894$650CC229-1E70-41A6-9200-18D1954D788E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa5d19ca26f4a639b33073019cfb65f01079159f","datavalue":{"value":{"entity-type":"item","numeric-id":5415482,"id":"Q5415482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2943894$86CF86EA-0B00-4C98-A384-AFC7522AB304","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"853cca7338917c54279472cd3d8107590a24e419","datavalue":{"value":{"entity-type":"item","numeric-id":1332662,"id":"Q1332662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2943894$7196988E-C9CA-4B2C-8164-64418D173678","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fac33fcaba991f9403b8d09b8ef4fc791c0a07e","datavalue":{"value":{"entity-type":"item","numeric-id":3549708,"id":"Q3549708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2943894$B4671FC1-C39A-4036-AA8A-8A00EF9651D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a2013da7a36b0c841b6254b17aed91599c6b8ac","datavalue":{"value":{"entity-type":"item","numeric-id":4507337,"id":"Q4507337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2943894$5F1D85D9-405E-41E9-924B-87208A55528A","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"bf5277d1ef1ff07305fedbc28c79087e4e81a592","datavalue":{"value":"Q130994121","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2943894$5046DBA7-2155-43B6-A039-97728FF6F228","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"050a6ec46dcd85ebc8afcdbeec3d47beb6da1db5","datavalue":{"value":{"entity-type":"item","numeric-id":5368748,"id":"Q5368748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"070b29d56ddba83d0707168adc975ca627c06ebf","datavalue":{"value":{"amount":"+0.8472323417663574","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":"Q2943894$4F01289F-0035-487A-B1DC-2A3C4DE8D3E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19ca86486705309b4cd62bf7986d549fce4c5d5c","datavalue":{"value":{"entity-type":"item","numeric-id":2931398,"id":"Q2931398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9fbf9017277a46941ae1cb49b01ee096d236603c","datavalue":{"value":{"amount":"+0.8433219790458679","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":"Q2943894$CA9A9CBE-5405-485B-98E7-EB966E2FF871","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22af9ce8516bf485396eefff569fbeb784812103","datavalue":{"value":{"entity-type":"item","numeric-id":3575151,"id":"Q3575151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"efe7358083ed863efb1fc92272c01ddfce55775f","datavalue":{"value":{"amount":"+0.8415834307670593","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":"Q2943894$AE09FEE7-ADF7-4E50-8DE3-A08806DB2B41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97147aae21537631ca1b904e4eadf6873ec7b909","datavalue":{"value":{"entity-type":"item","numeric-id":4652619,"id":"Q4652619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"edde83efa3b932d662127e09e435c6f1e8b45860","datavalue":{"value":{"amount":"+0.8368358612060547","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":"Q2943894$CEF86ADE-0BCF-419F-8187-0DF638EE486B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6416eaa359825598578289893f52010508dd9876","datavalue":{"value":{"entity-type":"item","numeric-id":2851860,"id":"Q2851860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51b66ecb90859ae5989ebfc7212e58130f30a332","datavalue":{"value":{"amount":"+0.8263306021690369","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":"Q2943894$81DC0D66-5256-421C-A05F-3AD9615B4258","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2943894","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2943894"}}}}}