{"entities":{"Q5077147":{"pageid":7106723,"ns":120,"title":"Item:Q5077147","lastrevid":56719278,"modified":"2026-03-19T04:50:09Z","type":"item","id":"Q5077147","labels":{"en":{"language":"en","value":"UG-hardness to NP-hardness by losing half"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7528581"}},"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":"Q5077147$B581CB6A-C8DF-4629-99B3-09B73403B690","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9a4ebfbd1f12eb5bb84842debed9f169dde5fd83","datavalue":{"value":{"entity-type":"item","numeric-id":3448784,"id":"Q3448784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5077147$FA8E49A1-9552-4B3F-B79F-828F299CDE4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc0f476358ab3d9fa7f8c58db4d920df08a5d274","datavalue":{"value":{"entity-type":"item","numeric-id":430831,"id":"Q430831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5077147$13A84DC9-86DA-4A6E-B7F8-8ACBA3B98AEC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"11632bef515b8b0af0e8d65098d262d28b5f8c42","datavalue":{"value":{"entity-type":"item","numeric-id":2816408,"id":"Q2816408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5077147$D025E455-A8E9-4987-B663-00BC35756966","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ed39cd09fba5cdf474042bb27d1349961ad549ad","datavalue":{"value":{"time":"+2022-05-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5077147$6C1A5D86-2476-4121-B435-1C941B3BA0CA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5077147$CD0227D6-4F78-447E-831A-655550B0BB5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f969879f531643f058f8dd4c87a7dd4eb7b8c4c8","datavalue":{"value":"68Qxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5077147$6132AB75-F0D7-41D4-A8F3-C9722945EFF4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d5536df8330aba9a9f0ae604a6033a36a04b0ce6","datavalue":{"value":"7528581","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5077147$AD859917-1484-4418-87E0-0D6FB25BDDB7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q5077147$29A4A8A4-335B-4C1E-92B5-F0274BE2435F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"51f95efbd0445c23f397467c5e509da28dd67bbc","datavalue":{"value":"inapproximability","type":"string"},"datatype":"string"},"type":"statement","id":"Q5077147$445BABD8-7C9F-4351-A62B-8C781AAFF999","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e088df1fc83158b6e99a19b8d624735c4cb0c49e","datavalue":{"value":"unique games conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q5077147$3E0340D2-68F8-424A-BF46-9A41618FB6DA","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":"Q5077147$96CD5870-2513-4614-939B-2D2D1C04BD32","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1de188d56e79c65970b4ff29c1e96c13f876cb38","datavalue":{"value":"https://doi.org/10.4086/toc.2022.v018a005","type":"string"},"datatype":"url"},"type":"statement","id":"Q5077147$BDBB1811-839A-4DFB-ADF7-EC92DADC1277","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4c5599a6d6626662c6c194bd376b5a00e6a1b9cd","datavalue":{"value":"W4226342274","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5077147$DC3DD864-58C7-43A0-B89A-42F50C034888","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4048b8fe3a5780e1b7090bd6b30ff1baf5f9135f","datavalue":{"value":"10.4086/TOC.2022.V018A005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5077147$8D97A614-1BC0-4269-A1D5-A512AFE7FD9E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1a68e63f31dd66fbb47319080c193dcf56ed16f","datavalue":{"value":{"entity-type":"item","numeric-id":5091753,"id":"Q5091753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc6ebcd0dc33f63d5952e318c385270e53174731","datavalue":{"value":{"amount":"+0.9862003922462464","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":"Q5077147$7ABE098A-CC48-4347-9253-A8F2FBE7B036","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45332b42e824d86aec5456ea97be8d1a865af671","datavalue":{"value":{"entity-type":"item","numeric-id":5415482,"id":"Q5415482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fcfb1aeead1fb7ff281e0d772e9bfc189f1dd55a","datavalue":{"value":{"amount":"+0.8402396440505981","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":"Q5077147$B2853CF9-7EB0-49B3-AF1F-055A1227C133","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d6271b5107ec015a4a60b8a08e464ab1f6b119a","datavalue":{"value":{"entity-type":"item","numeric-id":5230304,"id":"Q5230304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"998bd1bde2b82b7f5c4625e3e2102411e404aae2","datavalue":{"value":{"amount":"+0.8125053644180298","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":"Q5077147$DBCD1DA3-2EE6-47FF-8614-51F898953BE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7b68cd8dc765297fcc15e184cf5b03561914545","datavalue":{"value":{"entity-type":"item","numeric-id":4602398,"id":"Q4602398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a17b2450ba4aa7eba42b339d2e8049cd11ef6596","datavalue":{"value":{"amount":"+0.7927200794219971","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":"Q5077147$0912BBE2-6964-440D-BBD8-55E2CDD1EB71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75f6a7e82e70ee0d2ea710d4320ab27c04771144","datavalue":{"value":{"entity-type":"item","numeric-id":4636446,"id":"Q4636446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b467805b5dc51616f662546433b15d4fdfecb5fb","datavalue":{"value":{"amount":"+0.7911571860313416","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":"Q5077147$271FC7F6-4191-4CED-BA38-18ACBDB297FB","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":"Q5077147$8689CFA5-15EA-426E-A700-E6C7D8D8607B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5077147","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5077147"}}}}}