{"entities":{"Q868942":{"pageid":870790,"ns":120,"title":"Item:Q868942","lastrevid":50040457,"modified":"2026-01-12T18:42:57Z","type":"item","id":"Q868942","labels":{"en":{"language":"en","value":"Canonical disjoint NP-pairs of propositional proof systems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5129783"}},"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":"Q868942$2F6802CB-22D6-4733-9A0C-AA0BEAEE6B9D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"198f61692b89a35c86070d9a89a32d66c4dd4d96","datavalue":{"value":{"text":"Canonical disjoint NP-pairs of propositional proof systems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q868942$D78178F8-10F2-4BD0-B2BF-433489EE8384","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"07a9fd3e37941f44e05607cf9d054d14a3ad4264","datavalue":{"value":"1118.68070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868942$482222F8-13E9-433A-A879-B68508330F15","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0ee513048e71adb22fd9a8a028448fe040165ffe","datavalue":{"value":{"entity-type":"item","numeric-id":306279,"id":"Q306279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868942$2E8F5593-7AE8-4D04-91B6-B45DF1192E11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c67fd69af6c91517aae24d4f85769ddfc8b025e8","datavalue":{"value":{"entity-type":"item","numeric-id":652626,"id":"Q652626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868942$BBE3B536-2A5D-42EB-BD13-6E70879D039B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"29b02350197f27ae1879c4b07e2f60550fcfbf54","datavalue":{"value":{"entity-type":"item","numeric-id":161380,"id":"Q161380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868942$3110CAA7-0CBF-433C-B935-05848737D52D","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":"Q868942$B42174E1-227B-441A-B6F1-F5356FAD7E6B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0a3e704c51126050d068b3f11b9ffa0001836f09","datavalue":{"value":{"time":"+2007-02-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q868942$75369784-3A1E-4F72-AD4F-F9BF8DA50627","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868942$9D5BDC26-CF34-40EB-83D9-D875259A693D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ece9b879f80d96e2a1d45b28bdcc8cfa6b01861e","datavalue":{"value":"03F20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868942$0124C851-D2C6-444F-9FD5-A021F388A857","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6c0e0ea57fcf330975dd1f78127ceb07e43748e2","datavalue":{"value":"5129783","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868942$83301B31-2C5A-40A2-A32A-904A813CC544","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b3b279760df11662980b736532df7fbeff43d8ab","datavalue":{"value":"disjoint NP-pairs","type":"string"},"datatype":"string"},"type":"statement","id":"Q868942$0985BF2F-1CA9-475D-B897-438E47B46F8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b24e51e460d663f6ecf18860b761adb8bb29e572","datavalue":{"value":"propositional proof systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q868942$123711E3-B680-492B-A527-0E51870851DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"69ea5b69d0be7e1d5aded4795bf1838bfcba2141","datavalue":{"value":"degrees","type":"string"},"datatype":"string"},"type":"statement","id":"Q868942$2C0BF0AB-5678-454D-B67E-CDAD8DC3F365","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c550e66900f45d5e47eed88ca82a0fe67982e4b","datavalue":{"value":"P-separable","type":"string"},"datatype":"string"},"type":"statement","id":"Q868942$DE577604-A669-4D7C-AB4A-C634BDFDBCEB","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":"Q868942$EBE6CBF3-723C-4B65-937E-34B313C13A6E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7ebc0714097366c5c277bb246bd02a2574c66d94","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2006.10.006","type":"string"},"datatype":"url"},"type":"statement","id":"Q868942$FA53C7D4-5BFD-4B16-8B54-94A99DD09DFC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d80fab5ce49c7e31f19a6e9b822be2923bbc3a5b","datavalue":{"value":"W1979054927","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868942$443F3ED5-719D-43BD-A98C-5A991634203B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bea75da9fa67a5f77faa9362cd4aa6c737c792a","datavalue":{"value":{"entity-type":"item","numeric-id":4194955,"id":"Q4194955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868942$FEE94799-0141-4CE8-9589-DE64D6A10CC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f39e3c342e66df036e61e224b5255faaf947b35c","datavalue":{"value":{"entity-type":"item","numeric-id":4165426,"id":"Q4165426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868942$99ECFC7E-527E-46AB-BE3C-7483E3F25A91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1aa96b7c0ec9bc7a683e7636e258c3fded01e42","datavalue":{"value":{"entity-type":"item","numeric-id":3787917,"id":"Q3787917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868942$476034C7-ECCE-4926-AD3D-62B9870C11A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9d6d960e351c80be000f302db6efef14ab7325b","datavalue":{"value":{"entity-type":"item","numeric-id":4651518,"id":"Q4651518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868942$7C1CE12F-5CC3-46B8-8A03-559FE3B08AC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2daa63b45c7f3211b3d345ca4b37d012f1fd20a","datavalue":{"value":{"entity-type":"item","numeric-id":1190988,"id":"Q1190988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868942$87129535-28C3-4436-9D10-92F9D45616C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a2654c1ad3008ab65ddf962a999d4d8045dcdea","datavalue":{"value":{"entity-type":"item","numeric-id":4085242,"id":"Q4085242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868942$BCAE9C8C-CB1A-4F89-A2DA-3E91473463CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e58bbb4baedb91694badee957c4fb3ddac1ebd5","datavalue":{"value":{"entity-type":"item","numeric-id":2784495,"id":"Q2784495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868942$BCD1F896-E41E-4FF7-AE37-03442276C961","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"572a0ee44349c2469ef3719e0ab87f3436d9e7dd","datavalue":{"value":{"entity-type":"item","numeric-id":4708605,"id":"Q4708605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868942$25582B75-C01F-4D3F-9C67-CBE71F64575E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"683216a55837ad090f7ccc5703c9de7c068979f1","datavalue":{"value":{"entity-type":"item","numeric-id":4779177,"id":"Q4779177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868942$CDFCE958-1DE2-4E7F-B20A-53583057DCE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d37793be3730796c8bd8943b2c004c4b13247fb3","datavalue":{"value":{"entity-type":"item","numeric-id":1401249,"id":"Q1401249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868942$DFB6C434-AB7B-4D66-99B3-3F6109C17F75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aba0de3b75117dfe261f81c9f5f4226509a524a1","datavalue":{"value":{"entity-type":"item","numeric-id":3312209,"id":"Q3312209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868942$9C616DD8-A2C1-4336-ABFD-DF93FE837387","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8cefd7574d6776aa0391d0dd90bd375c1811d3f9","datavalue":{"value":{"entity-type":"item","numeric-id":1164414,"id":"Q1164414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868942$0D4359EB-12DB-4FC2-B41D-DA28AC84E5E0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5a88cfa32d6612987aa63c1c817ce01b7f100a43","datavalue":{"value":"10.1016/J.TCS.2006.10.006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868942$D55F7627-6BD4-4ED7-9C1F-0C82A67663D6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80b229f27005b3ddd16863d120c83416fe77a57c","datavalue":{"value":{"entity-type":"item","numeric-id":5492875,"id":"Q5492875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e3d46f6bc2cf3645619a27b21fced2e833559c7","datavalue":{"value":{"amount":"+0.9867135882377625","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":"Q868942$8C3EABEA-F37A-4A85-A6EF-37FB246BB1CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3826ad06e418714f7e857c35ab8ff93ef3e11e84","datavalue":{"value":{"entity-type":"item","numeric-id":5898879,"id":"Q5898879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c478163c07318b1cdc0eff2e038d3ff7c3bc70cd","datavalue":{"value":{"amount":"+0.9021366834640504","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":"Q868942$F6F7193B-A8AA-47E9-8B53-3FF5A7C1419A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a553968c20f72dc4a7c04371e13f048cae8585b3","datavalue":{"value":{"entity-type":"item","numeric-id":3436752,"id":"Q3436752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"678167b7a0a25440686ddc71fa246479e3747911","datavalue":{"value":{"amount":"+0.883152961730957","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":"Q868942$D804A920-47F5-4B5B-90A6-FC88FF6A97FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c3009bf6e2654da8d64a16b7c1e819431c2634b","datavalue":{"value":{"entity-type":"item","numeric-id":3636159,"id":"Q3636159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e713cd1460250dbf90416a0b437c97f86100b166","datavalue":{"value":{"amount":"+0.882960319519043","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":"Q868942$27F35862-6E5C-418F-89CD-88B7250C167D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"613783461e0ed794462d84c60679b85594e71d3e","datavalue":{"value":{"entity-type":"item","numeric-id":884465,"id":"Q884465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6c87e6213b39d16d3b2ad7493d2929c9f2e2412","datavalue":{"value":{"amount":"+0.8809592127799988","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":"Q868942$7FAA9621-6DE0-4262-88E9-3989094CB856","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:868942","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:868942"}}}}}