{"entities":{"Q879596":{"pageid":881444,"ns":120,"title":"Item:Q879596","lastrevid":50093206,"modified":"2026-01-12T22:21:23Z","type":"item","id":"Q879596","labels":{"en":{"language":"en","value":"Comparing reductions to NP-complete sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5152424"}},"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":"Q879596$D5CCC1B8-393F-4580-B601-7EC63A7E374F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7eead573189d7441e80a97147cedac67bf05188d","datavalue":{"value":{"text":"Comparing reductions to NP-complete sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q879596$A2D8CF2E-E9B5-4165-ADD1-D1E929B05EFC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7dfdb04ef89029ad532c09fa8bfc3df319dffc0f","datavalue":{"value":"1115.68088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879596$4EFBCF32-4B6D-430F-8EEA-F1563CB48EF6","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":"Q879596$0C2DF0D3-55E5-4B7A-8F03-339E76D74F91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"717bd7e49187dccbd000704e69f42d17b3b2d5b2","datavalue":{"value":{"entity-type":"item","numeric-id":208054,"id":"Q208054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$69941FD4-6F02-45CF-8BD5-0006A884BE0E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$4D03C995-AEE0-43C4-B7D1-B8BC6A01A822","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1a2af428023bb1f64e3e9e7c392bd08e7b812892","datavalue":{"value":{"time":"+2007-05-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q879596$98F8CC83-6F43-4991-B157-36EB8F7DBBF0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879596$5E485069-9509-456E-B00A-BC0A3E06B360","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879596$CBB6812A-B8F7-4B9B-9FEF-0E4A90382738","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c13fbdd16ba422b9cdfe12460529dd60d03089e0","datavalue":{"value":"5152424","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879596$0D874CF5-2FC0-4142-B4AC-BB595F8D85AF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63e5a4758c082c5f3d1e3d6a15cb3982fab85104","datavalue":{"value":"nonadaptive reductions","type":"string"},"datatype":"string"},"type":"statement","id":"Q879596$C980D154-1DDC-4076-BC27-008A89E98C9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"56808ccad9a530882079f682bf8f4b0eeb33d214","datavalue":{"value":"deterministic reductions","type":"string"},"datatype":"string"},"type":"statement","id":"Q879596$5506BB9E-6B00-4394-8635-1ED0B8562971","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a428018fcb62c231dc4b5243845a1705be4384e3","datavalue":{"value":"polynomial-size circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q879596$6AC7A98A-1F56-4B7C-BDBA-3ED9280EA5C3","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":"Q879596$D878B586-2BA6-4D0F-93BA-B0D78518D43D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4af1cd9090e323e78d5e2d1912acc6f5cf5cff32","datavalue":{"value":"https://doi.org/10.1016/j.ic.2006.10.005","type":"string"},"datatype":"url"},"type":"statement","id":"Q879596$D37EF19E-C590-42B2-B20A-5F38C81BF2FF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"368a999c2e92f6e645ac26f6118f21e289d89551","datavalue":{"value":"W2144718727","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879596$27D82109-7607-435C-B16A-04B2583A58BC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"898f7abebb2110166fa4d903fdadc4d54bc027a6","datavalue":{"value":{"entity-type":"item","numeric-id":671427,"id":"Q671427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$13D02CD3-4CA0-4799-9F53-6FC442C0D8CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2287ea70716fc40f2d1ac564c031496968b69b1","datavalue":{"value":{"entity-type":"item","numeric-id":1097692,"id":"Q1097692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$1E63429F-F5D0-4611-8420-D0D9290460E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5377083d1b3660d9d5bc7fd8652be0d666ec388d","datavalue":{"value":{"entity-type":"item","numeric-id":3979608,"id":"Q3979608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$5E9479A4-B6CE-423D-8015-5F0AC4010DFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"618602aa0f10419153676886fd3da06a8ac6a145","datavalue":{"value":{"entity-type":"item","numeric-id":5929911,"id":"Q5929911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$C995B627-25E1-4D29-AC15-2D7C36A6A6A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9e2500aa25ab997555cb930c8e22654d1612f9c","datavalue":{"value":{"entity-type":"item","numeric-id":1887166,"id":"Q1887166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$A024C3B5-F84A-4D12-8992-9AFCA220FC3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99c820fd50baf4b0b751de885aa91162fc0b309c","datavalue":{"value":{"entity-type":"item","numeric-id":2480744,"id":"Q2480744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$6A13A67A-F513-404F-8827-7E0A6F4AA7F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecb9b7e017fc45acb5cb1d99b55a4850b0de87dd","datavalue":{"value":{"entity-type":"item","numeric-id":4359463,"id":"Q4359463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$9307838A-94B0-4ACF-AB0E-D1F9EE740C3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b29b54e2ea6bebe2474343664b5bd8d507b3ef7","datavalue":{"value":{"entity-type":"item","numeric-id":4218523,"id":"Q4218523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$17A85E74-A79D-497F-872F-3360183BF256","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c9985f6f87a12e675c0a4ce5a1c70bbd22a418a","datavalue":{"value":{"entity-type":"item","numeric-id":4266481,"id":"Q4266481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$A7548CF3-9CF7-40E4-926F-4FAECF5D4D00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47bb5430fb40b4bd2ad7cce5d1c1c335b17aafe2","datavalue":{"value":{"entity-type":"item","numeric-id":2784487,"id":"Q2784487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$669738D3-1692-4331-9A5E-C916F362A63B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc8a23ffeba96b222302a8fc88634877c986e670","datavalue":{"value":{"entity-type":"item","numeric-id":5465865,"id":"Q5465865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$C78E14DC-D565-48C3-A757-99783D3356D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"667a6e9c49d9f043a407f44eeae9ec32fe552c1d","datavalue":{"value":{"entity-type":"item","numeric-id":2784485,"id":"Q2784485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$708C9D8E-B99F-47EB-B0C6-D57FB27336C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8863af9731cf8129e05842f4a6fdb97182b619c1","datavalue":{"value":{"entity-type":"item","numeric-id":290182,"id":"Q290182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$9A513FEE-0AE5-40EE-A98E-3515BD8F10C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef5307938c6a9cade6a308372c55f6b4c9851188","datavalue":{"value":{"entity-type":"item","numeric-id":1262762,"id":"Q1262762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$0036D219-1793-4A4B-9666-90122F4E6CC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45543575358fa9f936229ea1980f01498db37989","datavalue":{"value":{"entity-type":"item","numeric-id":4128010,"id":"Q4128010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$EC909947-6637-4EFC-A8CA-79651DBF4507","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"131ed90b53be5117d36fba78f3a4384956c57317","datavalue":{"value":{"entity-type":"item","numeric-id":4016403,"id":"Q4016403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$A655C645-2ECF-424D-96FA-54F0677C9356","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d38b4a76df166b15ffd8426406cd56803e157294","datavalue":{"value":{"entity-type":"item","numeric-id":1190985,"id":"Q1190985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$A302C930-6AA9-4603-ACB4-A840F4BCDB12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0a8c80fa018cac3e15747981e6c5267473edde9","datavalue":{"value":{"entity-type":"item","numeric-id":1392022,"id":"Q1392022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$B5D2990A-D824-4146-B1F2-D1C2AC522E7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e5613ec75f7529c859b1044ac559c162c4a5d5f","datavalue":{"value":{"entity-type":"item","numeric-id":1426007,"id":"Q1426007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$5F4154F5-17A2-4E07-A3AC-AF37D7431B9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a1f1c8eb0e3042557a6d3a12709c7fedd7afdbe","datavalue":{"value":{"entity-type":"item","numeric-id":1374784,"id":"Q1374784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$222AFA6D-8E30-41C3-9A3C-E7CD95F69630","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f3f8c402957e2c95095405c7dd38cb2d24866a8","datavalue":{"value":{"entity-type":"item","numeric-id":1149766,"id":"Q1149766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$EB3C539E-4689-4E1F-ABD8-20F631B32C93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"742307b6c5e2acabf5fff706097abb1b1c0d7f4d","datavalue":{"value":{"entity-type":"item","numeric-id":4359459,"id":"Q4359459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$BDEA8AE1-D7CA-41AE-BB03-BCA78D0307AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5d817fcded45c0d7d6169802a7ae39651b45a7a","datavalue":{"value":{"entity-type":"item","numeric-id":1276160,"id":"Q1276160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$7AD3F1A3-548D-412D-AB2D-C63974C24D41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"201b483419d48c5270a3b2863ec2d0b5ec517a16","datavalue":{"value":{"entity-type":"item","numeric-id":5957724,"id":"Q5957724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879596$AD994908-127A-479C-8140-B6A20F304DD1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"71a00cf4652dbd6d1d3c2e8cf2823cda123e715f","datavalue":{"value":"10.1016/J.IC.2006.10.005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879596$9B5CD68A-6A08-4E5B-A8D9-DAE75651F478","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c45280ddfb92c7fdfc1f6443f17c1661186fc8eb","datavalue":{"value":{"entity-type":"item","numeric-id":3613782,"id":"Q3613782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7be5b5124c239ef2b3e6ca0432389be2766a3dbf","datavalue":{"value":{"amount":"+0.991704285144806","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":"Q879596$B2DE974A-4716-4E18-B6F8-2BA444B2153F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e69db4af34e7ecaa15328e34799e1295a2a32445","datavalue":{"value":{"entity-type":"item","numeric-id":671427,"id":"Q671427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9cb96918231716ef486512471894d746307b8ef6","datavalue":{"value":{"amount":"+0.8277661204338074","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":"Q879596$5C6400D1-BEDF-4819-8BA5-A98010E22BA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ce60a7b12a52d81f977c6807db10402fac1fae8","datavalue":{"value":{"entity-type":"item","numeric-id":4256649,"id":"Q4256649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e139cb54ac8cc11625088c878be89155d8891d22","datavalue":{"value":{"amount":"+0.8136513233184814","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":"Q879596$277D375D-9ECD-43FE-9F76-AC684681465A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08e6d9c9f089659f34ed51aeccace6fcd6181f03","datavalue":{"value":{"entity-type":"item","numeric-id":1097029,"id":"Q1097029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc1a02378b342abf3418f53e78da5278edb4c096","datavalue":{"value":{"amount":"+0.8098374009132385","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":"Q879596$0BCB5A03-B79B-4B15-8652-275F92F7DCFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aff5edd8f4f14ad43dc7a161a6f15988cddedb0f","datavalue":{"value":{"entity-type":"item","numeric-id":2763492,"id":"Q2763492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"740aa48d63ea20c5f4bf0c3a12f3194cd3848483","datavalue":{"value":{"amount":"+0.8089991211891174","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":"Q879596$A1266479-7B9B-45EF-9DCD-A4BEFEEEDAD6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:879596","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:879596"}}}}}