{"entities":{"Q671427":{"pageid":673276,"ns":120,"title":"Item:Q671427","lastrevid":63600522,"modified":"2026-04-11T14:16:07Z","type":"item","id":"Q671427","labels":{"en":{"language":"en","value":"Cook versus Karp-Levin: Separating completeness notions if NP is not small"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 983294"}},"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":"Q671427$ECE6C480-4B84-4320-98FF-7922ACF59978","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d5723fbb676aaa900f19f1af0e19d681f614b5e1","datavalue":{"value":{"text":"Cook versus Karp-Levin: Separating completeness notions if NP is not small","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q671427$CCB614C7-8520-42E9-A5F9-AEE9C6742F5F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c87e16311acd3863b896a6f455a8a2b5d43d3a81","datavalue":{"value":"0871.68083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q671427$98BAB3DC-B085-4A0A-B58D-E3AB20CE3374","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5c165fee937ae1aedfb799ad22aead52fa95bd78","datavalue":{"value":"10.1016/0304-3975(95)00189-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q671427$150AF60C-4480-4BA9-863A-6243A4FB98AA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"419b7313d3a3ec11007a12a6e35a79e5588c6081","datavalue":{"value":{"entity-type":"item","numeric-id":400420,"id":"Q400420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q671427$40DB4B80-0D4C-45BC-AC0D-6D48AA5D05D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7132138654ffdb26c08285530d848829d99f2a92","datavalue":{"value":{"entity-type":"item","numeric-id":400421,"id":"Q400421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q671427$3703C86E-CF94-441B-A37A-4E56AE8A3105","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q671427$1BE2B0E1-2AB1-46E7-B3FD-86B6608A4AB9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b79c82e669aca3d97718bc55c57512b326a2a4ab","datavalue":{"value":{"time":"+1997-02-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q671427$F2A9B3DD-E401-4076-8BFF-C73E20299070","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1855ddf3513fb2625a26231838468d8afac2b6c9","datavalue":{"value":"https://lib.dr.iastate.edu/cs_techreports/109","type":"string"},"datatype":"url"},"type":"statement","id":"Q671427$34473FE2-D383-45C2-94F0-67973C6D8BD3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q671427$2A53BBAC-E9B3-4072-AE44-08634EEC7629","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d19786a449830dae26f7dd9633d987e01db30346","datavalue":{"value":"983294","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q671427$25A50216-DCF0-4BC0-B729-5B7D2F742120","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q671427$D48AFD00-C6E9-4C9B-83E0-9AF45869A277","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"527dca14f8c417c78f1a0b10f900b007ac776bee","datavalue":{"value":"Cook-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q671427$52106601-0045-4375-ADE4-90C0EAADD9D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eec2bdd31a4f6379f917ce5fbdf39b30a571f857","datavalue":{"value":"Karp-Levin completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q671427$902E6DE1-6AE5-4C98-A63C-2B2CE9B2FEF1","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"8978975c708555599f4de055ad7016df1bee674f","datavalue":{"value":"Q60578985","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q671427$B5A37D82-F5C3-4C45-8E76-3C742B62A718","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":"Q671427$55C095F6-3F03-4B36-8293-7B243BE761E7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1eb7cd79610524fd817ebf37fc7a975628846a6f","datavalue":{"value":"W2080139332","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q671427$D6A43A4C-23B2-4FB2-91E2-ABF981BCAFE5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3aef7f1de44fc085d5fa0e8017fc61e6796af602","datavalue":{"value":{"entity-type":"item","numeric-id":4286231,"id":"Q4286231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q671427$848C101D-D9B6-4A86-88F0-F8464FADA752","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":"Q671427$BB741BE2-F49E-43A3-BE07-1632E7605EC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb09716bd57a1011f7c259b1047b4d21b39a969d","datavalue":{"value":{"entity-type":"item","numeric-id":4775472,"id":"Q4775472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q671427$4B0923F0-AC31-45FD-80E3-5C8F551F56FF","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":"Q671427$E884FD3E-734D-4150-A95D-144EE1B236DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef757ecac8e00102e8fe2d81d7657ee3391ff698","datavalue":{"value":{"entity-type":"item","numeric-id":4138187,"id":"Q4138187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q671427$390C9124-83C5-4354-8A4A-F53650C72361","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0c0eb0e580a2db7274ff2f44840ea750a4689e1","datavalue":{"value":{"entity-type":"item","numeric-id":4834381,"id":"Q4834381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q671427$1D89E24E-9B1E-4088-87E6-C1201BECDC0C","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":"Q671427$1D068957-6AB3-4ADF-8A8B-43BB2AE4B4C4","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":"Q671427$A6C27E73-AE90-4F0B-B606-DEEC1ACACC91","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":"Q671427$4EA09B65-5AC4-427D-961B-F9DF52D1F406","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a66a579e1cbbdf800611294dda0dfa180c6508c","datavalue":{"value":{"entity-type":"item","numeric-id":751812,"id":"Q751812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q671427$B332ED8F-C8B5-435C-B196-E00870F3F874","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":"Q671427$AEB1C99A-DA82-4119-BD0A-FCD8D12471BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71f235ba32c2312416178e80711d9affd8fc874d","datavalue":{"value":{"entity-type":"item","numeric-id":4305356,"id":"Q4305356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q671427$26448CAC-3776-4D2F-8BB9-BCACCF73D09C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4b1c731f12bfd44cb2a2bdeeda67137003fa296","datavalue":{"value":{"entity-type":"item","numeric-id":1349712,"id":"Q1349712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q671427$FBBBD80B-87CE-48E8-A62A-8BBC5EE6CB5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba48c6dd75052862185f5069e893f6b665add1de","datavalue":{"value":{"entity-type":"item","numeric-id":3978778,"id":"Q3978778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q671427$84757909-A469-496B-9FF5-5CE07BD611CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50fcf5981ae589f600261cdff81132ea97e61a11","datavalue":{"value":{"entity-type":"item","numeric-id":3751007,"id":"Q3751007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q671427$60DA0312-25AF-4AE8-97F3-C9B5F769A330","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09d55ef340103f0dbd2122b2c565ade17ce74f3f","datavalue":{"value":{"entity-type":"item","numeric-id":5587565,"id":"Q5587565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q671427$798D0EA2-CB61-4775-8B19-20A3E1984586","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4afe42b4065573d917224468528bb218cd3634b","datavalue":{"value":{"entity-type":"item","numeric-id":5634706,"id":"Q5634706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q671427$0289F796-6D64-4399-A9B8-730FEF1025E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fed5fd3a0c1f3a22e44e4e1257dfbceb7db271a9","datavalue":{"value":{"entity-type":"item","numeric-id":5616138,"id":"Q5616138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q671427$3CF89EAB-BC3A-41A6-BE0F-3F5468AE8DDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ee90301292f993937476af8a941fa54b3796566","datavalue":{"value":{"entity-type":"item","numeric-id":2264549,"id":"Q2264549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q671427$E086ADD1-3C36-4780-8F69-CC38693E563F","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":"Q671427$967AF35A-359D-4D10-9522-A33E3C20D090","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":"Q671427$1D05B450-0EEE-48E6-A92D-6CBA6E9B764D","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":"Q671427$C934EA9F-6CBD-4732-BCF3-7E417C3EFB9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63bb2a41b8759d14a321fa0ecbd22ef0fa817da3","datavalue":{"value":{"entity-type":"item","numeric-id":1193869,"id":"Q1193869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q671427$73222020-1C1C-4260-B5AF-F57531A93597","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"9125f010a18f54574afe7f74b746e2a84aa7459a","datavalue":{"value":"journals/tcs/LutzM96","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q671427$09701C3D-E886-40C5-8F5F-4DE48B3C2D36","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70509b0580dfb16e8f0c1b707e37967043f0c8fe","datavalue":{"value":{"entity-type":"item","numeric-id":2978535,"id":"Q2978535"},"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":"Q671427$03D7531E-05C0-4EAC-BF3D-33E5AF33FBF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"170cdb3aba648cfbc9313250beabf51cfbb4ab92","datavalue":{"value":{"entity-type":"item","numeric-id":5929911,"id":"Q5929911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c279cf22e0c79c7babc03e773aa8b7fae982f58","datavalue":{"value":{"amount":"+0.8576106429100037","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":"Q671427$46E57D04-835C-49B0-AB88-9CD7FA45DC13","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":"e585da46a296359dd0928fa10430a63885a22fa6","datavalue":{"value":{"amount":"+0.8571531772613525","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":"Q671427$ECCB59E7-2835-433A-B133-5EC63AE7F6E9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Cook versus Karp-Levin: Separating completeness notions if NP is not small","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Cook_versus_Karp-Levin:_Separating_completeness_notions_if_NP_is_not_small"}}}}}