{"entities":{"Q4601894":{"pageid":6631477,"ns":120,"title":"Item:Q4601894","lastrevid":58294755,"modified":"2026-04-04T14:51:31Z","type":"item","id":"Q4601894","labels":{"en":{"language":"en","value":"Autoreducibility of NP-complete sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6829383"}},"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":"Q4601894$3C24073F-C811-4AC5-BD15-D64C8DCF4356","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8e297c24362638dd6fa86aaf80a0c05cdf675e79","datavalue":{"value":"1388.68087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4601894$121F44EE-8E63-4E5C-B290-1472A8D5876A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3ee1f3cf09e866f3eab6561711e5db4300ad48b0","datavalue":{"value":{"entity-type":"item","numeric-id":596116,"id":"Q596116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4601894$494D8AEF-A6DD-4715-898D-3E23BD2334E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"76c020312f965ee2daa4b4c0f02fb2244c74ecd3","datavalue":{"value":{"entity-type":"item","numeric-id":1745960,"id":"Q1745960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4601894$F9A4D870-BC97-4D10-9CD3-F62C5728AB00","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1335161379199d9038091fb354c2f0e9ba953e5b","datavalue":{"value":{"time":"+2018-01-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4601894$F210934C-EB30-4D33-AD19-3B34E3D85DA3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0fd36cb8c7ebcc851f00ad50a96114288c512e99","datavalue":{"value":"https://arxiv.org/abs/1601.05494","type":"string"},"datatype":"url"},"type":"statement","id":"Q4601894$2C25AB9C-5190-4BDF-BCFB-6C7FB3A84ADF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4601894$3C83D3AC-817F-4787-AC76-A4F012030473","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"379be2ae88ac653823960287ba517e23fc9265f4","datavalue":{"value":"03D30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4601894$2C60BCAE-9CB1-48EC-8744-AE69C4C533B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4601894$A882B005-1483-4F07-9704-16F4468B4892","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"708b9aaf979d3906ac0c04e9685bbeb10f9ba1bb","datavalue":{"value":"6829383","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4601894$39D218F5-0801-44AA-8EC3-3A5BEA5DFB92","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q4601894$3755051C-082B-443B-B67C-BF2B006C2EB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q4601894$59BF811C-CD05-44D9-8F2C-B64C267B2259","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"07b71510b51145facbe4cef602534d2599dba38b","datavalue":{"value":"autoreducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q4601894$E14DD139-B61A-4876-AA62-D08D51A37B18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"92c6235562dc0eab11f092f0fd132bb65aa6d603","datavalue":{"value":"genericity","type":"string"},"datatype":"string"},"type":"statement","id":"Q4601894$7AADE534-1E5B-4E50-BBB9-E4E56F622E69","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":"Q4601894$BC2DBC83-1342-472B-A2DB-B2561DE3C36A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bf43d47a61b32a19b06841d34fd9348df8b6fd2b","datavalue":{"value":"10.4230/LIPICS.STACS.2016.42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4601894$20A87B72-8E03-4233-AFCC-D7C16A18F394","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b65a5b8025e1a151ad9f0c6938315d4552e437e4","datavalue":{"value":{"entity-type":"item","numeric-id":1745961,"id":"Q1745961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8d7e66ddba9e8bba0bb9b26375d0f5cdb29bf9c","datavalue":{"value":{"amount":"+0.9874013066291808","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":"Q4601894$B9D462BD-B5EE-4771-94DD-F238D24AF15C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb832460c9f35e4f7bf53263c52255199066f86c","datavalue":{"value":{"entity-type":"item","numeric-id":2794381,"id":"Q2794381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2f0b209f48580c548712ffe048cb4051b3130a6","datavalue":{"value":{"amount":"+0.8505128622055054","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":"Q4601894$6BC34ED4-F5B0-4BB8-BADE-8168E25F3778","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a02a1e2bae5918f578f4338f41acebd41dab46ad","datavalue":{"value":{"entity-type":"item","numeric-id":881593,"id":"Q881593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88a2b64e04e37d956488a747b923c0b3113ea981","datavalue":{"value":{"amount":"+0.8486616015434265","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":"Q4601894$71587BEA-279C-4E5E-8C0A-88FBD9A0A8A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3254258d399b99d6db03c8bc6998f16fafee8b61","datavalue":{"value":{"entity-type":"item","numeric-id":4943880,"id":"Q4943880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea7c15fc25560dd1d199a9dfb5f7f050c85e74a9","datavalue":{"value":{"amount":"+0.8431947231292725","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":"Q4601894$66B08A34-1F2F-4BB8-B0E5-A70ED82C6571","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"762f764aba4e743b1e95274db89089b2e0502b4f","datavalue":{"value":{"entity-type":"item","numeric-id":5492867,"id":"Q5492867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea7c15fc25560dd1d199a9dfb5f7f050c85e74a9","datavalue":{"value":{"amount":"+0.8431947231292725","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":"Q4601894$1B56CED9-106E-4949-A3A6-934BD79553C8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4601894","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4601894"}}}}}