{"entities":{"Q2875151":{"pageid":2885871,"ns":120,"title":"Item:Q2875151","lastrevid":52065236,"modified":"2026-01-20T21:04:18Z","type":"item","id":"Q2875151","labels":{"en":{"language":"en","value":"Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6330064"}},"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":"Q2875151$24F1434B-0012-483D-A6BA-F56FD3E60C86","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"81561aa600d682d2cc496ba6a6f04b3867822f21","datavalue":{"value":{"text":"Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2875151$10D0420B-CFF9-445C-B509-4C00838E4FBA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6a459f40402e3a64e2e67bc4bf9e9313fe6acdce","datavalue":{"value":"1293.68132","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875151$3B003556-9313-47CA-8501-9877638D5B6A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"797146a96379d65eca67bc74b3005301479c2dda","datavalue":{"value":"10.1145/1806689.1806725","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875151$27FDEBB3-D25A-4EB7-AB74-68872598EF3F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dfb3ff06d109b1edae59c508e43e1eea36ca2170","datavalue":{"value":{"entity-type":"item","numeric-id":309800,"id":"Q309800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2875151$587DE99C-A9B8-4411-9331-4ADF13E0EC17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7a25d963ba8459ff509d0f0ec3595c17b9f7f836","datavalue":{"value":{"entity-type":"item","numeric-id":354650,"id":"Q354650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2875151$3E142FA2-99DB-4FAD-A5CA-C2584AC9322F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"857e6d765dc12abc2ea24a145570b777b4cfba51","datavalue":{"value":{"entity-type":"item","numeric-id":2875127,"id":"Q2875127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2875151$5A7F9863-7123-4644-8EC2-EA6B473E5EEF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f80e145b44ef7aa11a9e241ede63c58486ab29d7","datavalue":{"value":{"time":"+2014-08-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2875151$3415AFFD-31B2-4EE6-8638-0AF3CE502F3D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c2de69782926e15b55e598dd04de8137d7ebb158","datavalue":{"value":"https://drops.dagstuhl.de/opus/volltexte/2010/2504/","type":"string"},"datatype":"url"},"type":"statement","id":"Q2875151$09969F14-7115-4760-983B-4F7F6A9EFB62","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875151$29818AB5-CB01-4284-9D7A-E5EE92D25A51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875151$6BF8201C-0FDE-4D9A-92C7-280603555554","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875151$35BA0F65-EA6E-4C7B-A6B4-93FA36C02842","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875151$E5336287-1DE2-4B4F-8519-35E7521D734A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875151$D4B2A38E-95B7-4EF5-8BBD-E70D18685BF3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8d4130b7418aaff36151e0ba98461180ba85ff42","datavalue":{"value":"6330064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875151$B24B4D72-6B33-4D6E-95BC-D7239128B246","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84908b5e6b7d4855884fb3e19c557b8208d2fed6","datavalue":{"value":"arithmetic progression free sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q2875151$C6D0FF78-4EE8-4850-A38B-3BAE6E5F4F9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9c52f7b4a553b1787b81b760bd70e732f8e5abf8","datavalue":{"value":"feedback vertex set","type":"string"},"datatype":"string"},"type":"statement","id":"Q2875151$7604A82D-D499-4578-940E-700F709DFE38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f024f3ed5c37bb9ef1b1544f3e9177ddad08a0b","datavalue":{"value":"hereditary graph properties","type":"string"},"datatype":"string"},"type":"statement","id":"Q2875151$6CE7221F-267E-47CD-BC66-4CC56B1D95B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"040e5cadc2542137fa22dc2efc65268bb08b809c","datavalue":{"value":"kernelization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2875151$25B22D9D-79CF-4420-BA1E-F7381A49D294","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee63604621b6fd9d90b10f19ccdd9c167a66b1b6","datavalue":{"value":"parameterized complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2875151$28479D2D-69FC-4662-8A37-11AA727023EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"198526b3e16365d088b0d8e8cb1a48a9c3937632","datavalue":{"value":"probabilistically checkable proofs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2875151$768B3DA7-77E0-4E32-B705-53D18354E0B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"252f9f9ed9fe8ca406cc19fba38a46c0414791ee","datavalue":{"value":"satisfiability","type":"string"},"datatype":"string"},"type":"statement","id":"Q2875151$D117F845-70B6-4CF4-A3DE-46E0417F64EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89064274a499b93f141ab8aab6929ae41a5ae460","datavalue":{"value":"sparsification","type":"string"},"datatype":"string"},"type":"statement","id":"Q2875151$78430135-9402-4652-A2E2-4E14BB20140D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aac385c43cc6d982a9dd1fbfee8ab2754a681c11","datavalue":{"value":"vertex cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q2875151$A53A4EC1-BC7A-4F4B-92EB-5DF3AE5944E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cae6cb6e44d52cfa0441a707e419fa504a5daec8","datavalue":{"value":"vertex deletion problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q2875151$4682F020-6A19-4AF5-9F20-10A6CF420361","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":"Q2875151$F01B4D45-87B6-437E-9586-6B601A2F33FC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"008f9198d0845b35e7c02a0d51e000d23e0d7da0","datavalue":{"value":"W2058258808","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875151$3BE8CBA5-6C43-41D9-AC26-23BC3FC56FC7","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"27793b7ab0ba6871f43bfdda61d970c748803d2b","datavalue":{"value":"Q130968380","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875151$1DE02C8C-2DC5-485E-8697-CF190B8B46CB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f59c5d73f898e6d8421ba00cb2cb3d4a535e3f1","datavalue":{"value":{"entity-type":"item","numeric-id":5501928,"id":"Q5501928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7bb98d2c6b326bc6cd9958225d18b09943a246b3","datavalue":{"value":{"amount":"+0.997303545475006","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":"Q2875151$087B240A-B4F0-463D-AE01-77AC15903D74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f4c356bde8b292ac2cbcb3869e6575707999de9","datavalue":{"value":{"entity-type":"item","numeric-id":2408194,"id":"Q2408194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a92846c4ad5382d12a293ace6fb7c99dd620c263","datavalue":{"value":{"amount":"+0.8007069230079651","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":"Q2875151$EEFAED05-B752-482D-888F-FDE50EC8B289","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d90f9a72948fa4502efb9e851a4e00a1db0fab9","datavalue":{"value":{"entity-type":"item","numeric-id":4608634,"id":"Q4608634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0607be09293e842e48585776937c627a4ad73099","datavalue":{"value":{"amount":"+0.7989006042480469","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":"Q2875151$8ADEB03F-8A41-4D35-B4F7-22A27E1B4531","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"965c616b98ea25e09db93cacc085639d828b3bfb","datavalue":{"value":{"entity-type":"item","numeric-id":5363770,"id":"Q5363770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab50f13a097f3f1d0f7754729787a97a7b6022a6","datavalue":{"value":{"amount":"+0.7974808812141418","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":"Q2875151$A7189921-A4F2-4ABC-AAEB-0F7C6D84724D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"706c2e7b52f58a577da252a7891ee74f91ecf61f","datavalue":{"value":{"entity-type":"item","numeric-id":5205824,"id":"Q5205824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b73e9073a0a900a69c831236d1d304c8fcea0a5a","datavalue":{"value":{"amount":"+0.7967479228973389","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":"Q2875151$35C21C2D-C6C1-4999-AE6A-5C1EEFA45DE3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2875151","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2875151"}}}}}