{"entities":{"Q2978535":{"pageid":2989260,"ns":120,"title":"Item:Q2978535","lastrevid":85656581,"modified":"2026-06-03T10:46:50Z","type":"item","id":"Q2978535","labels":{"en":{"language":"en","value":"Separating Cook completeness from Karp-Levin completeness under a worst-case hardness hypothesis"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6707786"}},"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":"Q2978535$26931E9B-0514-4B46-8049-B1DB792DE4BA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7f592ac911dcac22c5556d68021ede09bf0ce85e","datavalue":{"value":"1360.68482","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2978535$810B165D-9AFA-410E-B49D-31CC94E869BF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1cf67e3c5c14994a0c302429d66b3227022eece","datavalue":{"value":{"entity-type":"item","numeric-id":347121,"id":"Q347121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2978535$503FEA87-9AC7-4D44-8F85-6B181B57DE16","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":"Q2978535$82DDB134-5BC1-48FA-B0AA-33C8C400BB63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b51342a3fb7db7b4b0d9ea4e932547c6c81c98ff","datavalue":{"value":{"entity-type":"item","numeric-id":2978534,"id":"Q2978534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2978535$2AE7B2A3-F711-4853-B896-C4E7F0551DA2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"aa23cc0149fb181ddf62c54fcf7661372ca0f225","datavalue":{"value":{"time":"+2017-04-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2978535$7F52AE26-33D5-4D50-9B70-047790291861","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2978535$4CB6FE17-0C72-4585-AF8A-03EEDFF71E9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2978535$F941442B-6E8C-49F6-9614-EECB0717D0F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2978535$2C1ED2AE-A5C8-4BAC-9369-D0D22A16A1FC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"51c8683c8a49ccaa3077068e76d84b4be6ef02be","datavalue":{"value":"6707786","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2978535$1FE27953-BF91-44C3-B115-80849CCBE7A9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d83c2271da7b40be1b7bc6789f4eb528a4497364","datavalue":{"value":"Cook reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q2978535$F0C77DEF-B0F4-45FB-A618-12E134A9F0CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0465b31778b99ae164a895342a2a3b6892a5331d","datavalue":{"value":"Karp reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q2978535$8D72EBB9-6576-4AB7-A694-EEC03B3CE5C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2978535$853B8B94-AD5E-4C24-9BA6-7A363CCCEF64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b06994431796472ed4158ee258c2bd3e3aceb9f6","datavalue":{"value":"Turing completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2978535$3F4F8683-0243-4718-ADEA-EBA21F35DCD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8028fe0aa549ee0a8820b1b783e87afbbc19c0b","datavalue":{"value":"many-one completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2978535$60C5A5C4-EE98-4C10-9B8E-0B340847391D","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":"Q2978535$CA9AB4FC-4A4E-4B71-B236-1447EC35C859","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d4429658ace89e7d7eaffcf3cbe5da23b74d2500","datavalue":{"value":"http://drops.dagstuhl.de/opus/volltexte/2014/4862/","type":"string"},"datatype":"url"},"type":"statement","id":"Q2978535$10D5AF36-DA2D-4EF6-84B2-016DB4CF44AC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"10055a69c9850fbfe15ce92ed0cd47c485c5586e","datavalue":{"value":"W2246416211","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2978535$F2231D27-9BBC-4FFF-8938-F01C5BBE2E41","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0c5b229db3ed9e9a69923f828f33c042b0de323f","datavalue":{"value":{"text":"Separating Cook Completeness from Karp-Levin Completeness Under a Worst-Case Hardness Hypothesis","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2978535$C58BB340-0A1A-45CE-91F9-071A18A00659","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0cf6bf347f2c4fd454f102ec54cf180d3ac0a8b8","datavalue":{"value":"10.4230/LIPICS.FSTTCS.2014.445","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2978535$19467721-A522-4CA1-A0F4-D0EFC793A97D","rank":"normal"}],"P1643":[{"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":"c8202c693a7114ce68cd8594c64f51b6b2be744e","datavalue":{"value":{"amount":"+0.8864107131958008","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":"Q2978535$C15BAE21-EC9B-4710-AD23-1F4DF377FDEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3c3e0198f19e9e3d46579727f006c19993da67c","datavalue":{"value":{"entity-type":"item","numeric-id":3113769,"id":"Q3113769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"310be97eb13d98093509225a9fb26398baccf437","datavalue":{"value":{"amount":"+0.86422199010849","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":"Q2978535$B3DAB6E7-0540-4A8C-8B17-2DBB8C5A6F79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65487f5bac48e3e5c18b30b648b1ad9dbab73457","datavalue":{"value":{"entity-type":"item","numeric-id":693053,"id":"Q693053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f65b1aa05d282ee4d267f5cb1f00436dc98634e","datavalue":{"value":{"amount":"+0.8582724332809448","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":"Q2978535$1D58AC50-E461-449B-8EAF-6705500EF267","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07235933f75a48f5c57e3c9bfb4f382011172f6d","datavalue":{"value":{"entity-type":"item","numeric-id":2784487,"id":"Q2784487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73766095f18712592d1382fed32e8cd36c231128","datavalue":{"value":{"amount":"+0.8380001187324524","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":"Q2978535$BB31DFE8-ECF0-40B7-822A-BFBD0165FF03","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":"83a2f1875abf7cf94eb34dac74a69ebdd2785a91","datavalue":{"value":{"amount":"+0.8317037224769592","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":"Q2978535$7FDA2BC3-0909-4CDE-A1EF-9FD788544F3E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Separating Cook completeness from Karp-Levin completeness under a worst-case hardness hypothesis","badges":[]}}}}}