{"entities":{"Q751812":{"pageid":753661,"ns":120,"title":"Item:Q751812","lastrevid":64101582,"modified":"2026-04-11T17:39:26Z","type":"item","id":"Q751812","labels":{"en":{"language":"en","value":"Cook reducibility is faster than Karp reducibility in NP"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4178764"}},"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":"Q751812$F274A9CE-15B4-432C-8396-B83196499469","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9b15949fedeb88166d9def672bf638cb928a93ab","datavalue":{"value":{"text":"Cook reducibility is faster than Karp reducibility in NP","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q751812$78957A0A-F401-4BA4-83B5-43085260C87E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d61f31ec521397905723bb9b1199b3fee7aae466","datavalue":{"value":"0715.68030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q751812$5B6B0E51-14A9-4DE9-A90D-EF83FDAA2FB5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ac6d2344419849a1af25bb74b0f57133367d0f8b","datavalue":{"value":"10.1016/0022-0000(90)90026-H","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q751812$91C729EF-38D4-4738-B205-95229E699C8B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"547a70f32038f5698afdc474eeef7f9e925fba61","datavalue":{"value":{"entity-type":"item","numeric-id":699184,"id":"Q699184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751812$850B44D5-2E03-4F0C-82E3-4CFD3E6BAED5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751812$09CCE325-548A-4CF2-BE53-A64A475895F4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q751812$DD7EBE9F-3D89-46E8-87F9-9DE66FDA2149","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q751812$9A08FE09-7251-43B3-84F6-E3CAA4EF5CCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q751812$609CBFB1-8014-41B6-A3D7-29E0F8D782D8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ed037b5c4c6859d296305390d59d7edd30923704","datavalue":{"value":"4178764","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q751812$2075CE31-EAD9-4265-B000-3314BC75ECC2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0bc1cc50e8d4b517f651118878724606a4faacd","datavalue":{"value":"reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q751812$0CE275F7-9FDF-4BC3-AECA-019B71AB203D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"18b896e4875df610358fccf59713481feead9685","datavalue":{"value":"NP-complete sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q751812$63E96FA7-6CD3-4C78-8F3E-FCE77FDDB70D","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":"Q751812$4CFEBD64-6E8C-4FF6-BAD9-E44F38C32ABE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b7948d2ae997be513a92df2486b836c4e1eaa12","datavalue":{"value":{"entity-type":"item","numeric-id":5667480,"id":"Q5667480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751812$5ABAF3A7-418D-4339-8A28-AF995C154703","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc43c30cb36c93faf5938e583d3f64b490e4f521","datavalue":{"value":{"entity-type":"item","numeric-id":1394124,"id":"Q1394124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751812$7FB63606-2F29-409C-9B1B-7C85062221C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751812$28DE074D-4F35-454B-9C0E-78D27119B870","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3249023457b3007c791afda29b30dce9efc64b77","datavalue":{"value":{"entity-type":"item","numeric-id":1094875,"id":"Q1094875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751812$43844159-6289-4B7B-B176-F5E4CFA85C99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3c77053f249ea7e82cd40265fa301ebde3267a8","datavalue":{"value":{"entity-type":"item","numeric-id":3781091,"id":"Q3781091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751812$B9E9F032-46C2-4268-9365-BB877E07EC58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751812$48FFB395-A4DF-4E18-B79B-34E2368E3C52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb51cb599580481aadcbb3a7e805e65dbcbf5ce5","datavalue":{"value":{"entity-type":"item","numeric-id":1079364,"id":"Q1079364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751812$8A60B016-009D-4DBB-9717-D5DA68FB371F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751812$DDAFE165-331A-4ED8-B382-BA8C0E4D48B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5729674352df42afcb3727df7e5bbb4c13eb877","datavalue":{"value":{"entity-type":"item","numeric-id":1097694,"id":"Q1097694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751812$6D0DF562-A705-4369-A526-9CB9ECC0B7CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3da510a58b16c0736f10bd517df8e982dda6dd9c","datavalue":{"value":{"entity-type":"item","numeric-id":3922170,"id":"Q3922170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751812$0F023870-5ECD-45A3-9AD8-00D2BAEAA1B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a76ed5ecb6eacb4e8a7924286bb0f0149f0c54bf","datavalue":{"value":{"entity-type":"item","numeric-id":1109766,"id":"Q1109766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751812$E7A75F35-00BE-4E26-B091-85DAFD83B773","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7d15acf9b2dc594da15dc289088a8a93d59b4f8","datavalue":{"value":{"entity-type":"item","numeric-id":1223166,"id":"Q1223166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751812$7EF1D2E2-DA7C-4582-ABFB-850B50CBF864","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71f28db7f96068e5ce3938c306e6d15e9aefa614","datavalue":{"value":{"entity-type":"item","numeric-id":3915990,"id":"Q3915990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751812$F7429607-B893-4D55-BC7B-D4E0BE64F1A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8941439de739c4cd65cdb44fb63c71009c2cabaa","datavalue":{"value":{"entity-type":"item","numeric-id":1229713,"id":"Q1229713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751812$12CC383B-831D-4C6C-8C94-742C73123D01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c8f124158d7067e7483da2752260349cdfd2953","datavalue":{"value":{"entity-type":"item","numeric-id":5659521,"id":"Q5659521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751812$00F05E24-1D8E-4170-A448-8BD8B82F6B0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c19040a60a44db62995cb08427466942d64d95f5","datavalue":{"value":{"entity-type":"item","numeric-id":1077412,"id":"Q1077412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751812$24EACC77-3061-42A2-951B-20799F70F22F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32c9cf122d104d7332be7d6610d7ce2681b03b64","datavalue":{"value":{"entity-type":"item","numeric-id":3768398,"id":"Q3768398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751812$0118D973-9DBF-4215-A2F6-2A2F411C82E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d938e2cf16a516c25169e92ed68817a27d01f44d","datavalue":{"value":{"entity-type":"item","numeric-id":5845382,"id":"Q5845382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751812$5E6BE390-9339-412D-83C4-D8420A3AB3BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9635365b0780328d7ae22bc69b462e7144999d03","datavalue":{"value":{"entity-type":"item","numeric-id":5573961,"id":"Q5573961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751812$81E563C3-5556-46B5-AE76-EC8CF8E65DEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37bd93f050a29505d9954e41ab03268b153e49a7","datavalue":{"value":{"entity-type":"item","numeric-id":4190619,"id":"Q4190619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751812$46D942C4-6A4D-49DB-8335-71BA32449D7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd520b49bc58e84d7c227fcb0bc974b432f91cc2","datavalue":{"value":{"entity-type":"item","numeric-id":1166515,"id":"Q1166515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751812$12278CCC-69AE-4055-971E-8047044D9757","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1edcfc8f162dce621803913f4363a765362e71d8","datavalue":{"value":{"entity-type":"item","numeric-id":3819052,"id":"Q3819052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q751812$F646E41C-4287-405F-83D5-F2354DF65596","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":"Q751812$129D21C7-0346-486D-B948-C15B82C135DB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ee1b341f1af86e785bc7d3b3f3b886cbe9dc8453","datavalue":{"value":"https://doi.org/10.1016/0022-0000(90)90026-h","type":"string"},"datatype":"url"},"type":"statement","id":"Q751812$8AC83CAC-4CD4-4BED-A1E8-5C51137C1832","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"14b9d72db9fa11d73411c8dc69a14097423a4eb9","datavalue":{"value":"W1985343313","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q751812$DE70A842-7B3F-4C2F-AD26-EB40E27F066D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b13456fe5fe9e3550c2469657db4a6d3d1543bb","datavalue":{"value":{"entity-type":"item","numeric-id":1124342,"id":"Q1124342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46c2fe1f3d2cbb741ec218efb7a12f1dfb37ad4f","datavalue":{"value":{"amount":"+0.7973504662513733","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":"Q751812$CC308BC0-651E-4629-8A7A-417BA262AEB3","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":"4d1edb7ac126effd1790d54a19b8f22c44fada63","datavalue":{"value":{"amount":"+0.7913457155227661","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":"Q751812$0BFD6F8B-82BE-4661-9D4B-6B3080E651D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e44593c94b6e871b4255132d1814bec1f362656a","datavalue":{"value":{"entity-type":"item","numeric-id":879596,"id":"Q879596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8cb0ce825387682ddfb285f4470017e699060fca","datavalue":{"value":{"amount":"+0.7875430583953857","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":"Q751812$203D32C8-58E2-42DD-B032-E08B590C1F5E","rank":"normal"},{"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":"80c0c35347320f13b75759881ac760a826b41877","datavalue":{"value":{"amount":"+0.7871975302696228","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":"Q751812$4AF2989A-BD9D-468B-ACBE-60C06B32CD7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c2adc893ba0e353cc07a8405075284e7651ff53","datavalue":{"value":{"entity-type":"item","numeric-id":3335768,"id":"Q3335768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5d3f79f61c72b8dac0100310a40b86275a7f4f2","datavalue":{"value":{"amount":"+0.7821065187454224","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":"Q751812$46E5F9C4-0197-4895-9556-2FD96393FD3A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Cook reducibility is faster than Karp reducibility in NP","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Cook_reducibility_is_faster_than_Karp_reducibility_in_NP"}}}}}