{"entities":{"Q1604206":{"pageid":1614946,"ns":120,"title":"Item:Q1604206","lastrevid":68020758,"modified":"2026-04-12T20:54:39Z","type":"item","id":"Q1604206","labels":{"en":{"language":"en","value":"Which problems have strongly exponential complexity?"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1763402"}},"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":"Q1604206$AC4C8D91-9CA0-4FAC-B0D1-A6260E5B01E5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d53eafb9ad4ab744c70c1b68f770ea64ee1cfb12","datavalue":{"value":{"text":"Which problems have strongly exponential complexity?","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1604206$C95B6A63-8734-43CC-B4AA-36FD5A4E71A3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"55200d30d8623f098a390658691b89dd317e31c4","datavalue":{"value":"1006.68052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1604206$AB33FCE6-6F43-49D5-86DD-FEF9B8B9FEF3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"afbdf0b4b75e6a0dfd1ecc76c9480c04f5fced5d","datavalue":{"value":{"entity-type":"item","numeric-id":202088,"id":"Q202088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$032B9409-ECB5-42CC-9809-EC4576BFF14F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d72b6c9fa09679ee04e7df5acd3659b335857c59","datavalue":{"value":{"entity-type":"item","numeric-id":192223,"id":"Q192223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$961C568D-8AE1-4250-8ADF-28BCDC41E7F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c465af4ecae833b58ea5e6991be87836c3358f9f","datavalue":{"value":{"entity-type":"item","numeric-id":192221,"id":"Q192221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$9B12D94C-BB20-4E85-B604-99EA6C6E8B52","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":"Q1604206$30CCE58E-ECA4-42A1-AB7D-FD38F98F7CCC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"adb3ef540eac58911e63cf63f703d86d64686cb2","datavalue":{"value":{"time":"+2002-07-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1604206$C1051495-46DE-4296-81ED-DA9A186AFE69","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1604206$999C21EE-9100-410B-B40D-B84A39E73AEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1604206$199D8894-C2A4-4D0F-94A7-B2B2F808E1CC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8f02513c32d3d37ad6790cce1c62e043604add8a","datavalue":{"value":"1763402","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1604206$D82CCD8C-E4C5-4237-8A7C-4A7C245561EB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f54a77c89400d66d954179de9250a3caf095223","datavalue":{"value":"sub-exponential reduction family","type":"string"},"datatype":"string"},"type":"statement","id":"Q1604206$2E005A17-C03B-4E0C-B0D1-A3A7D5AC824E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c8c9e80036612c21ad2ec3b6579e3228fd2ea1e","datavalue":{"value":"NP-complete problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1604206$189D8FBE-170B-43CA-B476-ABA6EAA46913","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":"Q1604206$00246CEC-26FD-4C1E-9BAC-569DB8380BE1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f94da75d01fae45f8e3ea0edd9be730f90129455","datavalue":{"value":"https://doi.org/10.1006/jcss.2001.1774","type":"string"},"datatype":"url"},"type":"statement","id":"Q1604206$1D0644DD-C1DA-4179-9CBD-6CE63080AC2A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a0554ff1f8bf3f25ab3c9a2857d3b018d98d3aab","datavalue":{"value":"W1995725694","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1604206$E69A218D-07D0-4EA6-B17A-FF308EFB60D8","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"a5f55f528c3a412c257963d381e1b52a0da4c029","datavalue":{"value":"Q55891730","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1604206$2B96D531-89E5-4528-AF0E-A34B17CF00FB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae78a63a69a74848d5aeaa89bef60027b93de2fb","datavalue":{"value":{"entity-type":"item","numeric-id":1892937,"id":"Q1892937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$F6738216-44FF-479E-90DD-66A322277AE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"957892286a77298fd7faca30f1f60dbb53f94696","datavalue":{"value":{"entity-type":"item","numeric-id":1054720,"id":"Q1054720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$EF2D6E1B-7171-4379-9F71-9111FDE7972E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4799e5a32c687eea79d573479ff8c58240f3cb62","datavalue":{"value":{"entity-type":"item","numeric-id":4004078,"id":"Q4004078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$D01C220C-522D-4681-AAD0-577549967E2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7258962f550bf808b8ce0edfe0f9b2099a09d076","datavalue":{"value":{"entity-type":"item","numeric-id":4230322,"id":"Q4230322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$C339B139-42DF-4345-977D-E4D7D8A3A8C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f6f7cfe19c6bb4309c911e2b5e1f904d78cade2","datavalue":{"value":{"entity-type":"item","numeric-id":4252729,"id":"Q4252729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$D1778CA1-3EC1-4149-B15E-6369939B9C98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b87d4d660be017ed3a655c9578140dd400c43c7","datavalue":{"value":{"entity-type":"item","numeric-id":4385519,"id":"Q4385519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$DB108E1B-F992-4C27-8C5D-2685393EB887","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11eefd7e7dc86c1755a8db4c6825e6e9fdeb6d39","datavalue":{"value":{"entity-type":"item","numeric-id":3619797,"id":"Q3619797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$217A5DDA-C460-4E66-910E-F30E5DB3AAE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8e0b4cd545de1b25a641a46ca97c36b11096ea1","datavalue":{"value":{"entity-type":"item","numeric-id":4806606,"id":"Q4806606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$3580CECE-6148-4D51-B65B-B3BBEAB27E15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50e39951d487d3bf563c62341ed381ea5be4f484","datavalue":{"value":{"entity-type":"item","numeric-id":3318683,"id":"Q3318683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$AEEB1FA2-BB56-4C7C-9201-FF7510CF17F2","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":"Q1604206$E47C815B-573C-478E-937C-36D0F3679A45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00018817f9b68b5533d20e05f9bca37aee54a0e8","datavalue":{"value":{"entity-type":"item","numeric-id":4250220,"id":"Q4250220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$E078E50C-8C52-4FEC-9F9B-84BDE9F752DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"633481678a0836b3846b49aa8db13fb38104e9a2","datavalue":{"value":{"entity-type":"item","numeric-id":1082830,"id":"Q1082830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$5F5D0B68-4B71-4D19-99DC-FA97F5800938","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2bebba68dc7dfbaf1caac8cb5c43ad35be909acd","datavalue":{"value":{"entity-type":"item","numeric-id":4484662,"id":"Q4484662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$6F7654F0-6AA3-4257-8DB0-86832625CA93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ab505d079acae70f31b63226f0d6d40ff5b0dd0","datavalue":{"value":{"entity-type":"item","numeric-id":3546306,"id":"Q3546306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$E2F1420A-ED18-4AB8-A6EC-DFC52618B7ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"396e397662d41ab464556b8ad587e8bf14aa7d36","datavalue":{"value":{"entity-type":"item","numeric-id":4526973,"id":"Q4526973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$AE83A004-21FE-44EB-854B-906F602CED84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce6133d293bb8bfa149948ffdc9b0f276ef45523","datavalue":{"value":{"entity-type":"item","numeric-id":1186548,"id":"Q1186548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$FD77B450-5325-4B9A-9B13-DEC837B28185","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed28daf112121dc08adf4ce72a073bd046e54847","datavalue":{"value":{"entity-type":"item","numeric-id":2556406,"id":"Q2556406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$6157857F-2938-4D1F-A652-93205D2CA339","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c95d11951a8791c3fab2ea8429076d51956a1c28","datavalue":{"value":{"entity-type":"item","numeric-id":4283247,"id":"Q4283247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$34602931-961D-4C59-9C3F-AB3A54C8DBC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe51858e011b4c91e5d000190db8ea9f25d23d87","datavalue":{"value":{"entity-type":"item","numeric-id":5751941,"id":"Q5751941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$38352675-2EE7-48BF-B9A0-ACE9219C703B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e99241b4b615d193a50e0b859831e89601d1c0d","datavalue":{"value":{"entity-type":"item","numeric-id":4252414,"id":"Q4252414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$AB1A2F4D-8CD1-4E3C-9CDA-8BBE4A5A4E8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36d629883fe1d8cfcb493de168c946ca849ec332","datavalue":{"value":{"entity-type":"item","numeric-id":4164821,"id":"Q4164821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$2D9DEF82-30D5-4CEF-A89A-19AB5DACEA2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f18d643e8a69fccb17c65da0c1eca56483fd8e4","datavalue":{"value":{"entity-type":"item","numeric-id":4004139,"id":"Q4004139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$C0608EDC-F00B-4CF4-8F14-62B50E8DDDFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e55670eeffeb14e6ce51166fb8470acff9c12ef5","datavalue":{"value":{"entity-type":"item","numeric-id":5660314,"id":"Q5660314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$3881C80C-1BEB-4200-89A7-449480B0F8BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1dc8a1faedec1647ff5e9aefae185cf306f2bc5","datavalue":{"value":{"entity-type":"item","numeric-id":4133117,"id":"Q4133117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$4B4CD81C-252B-4103-8260-AFA66CA61DEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb905b79b8a8b710686969dae7565d6e29bf903f","datavalue":{"value":{"entity-type":"item","numeric-id":3777476,"id":"Q3777476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1604206$458A8786-C2AF-4C48-B605-B95D2007491F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c7312d3d6647286ee8a306c4d32549fa38a78289","datavalue":{"value":"10.1006/JCSS.2001.1774","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1604206$DA1D8289-99FA-4783-855A-86BF1377B2E4","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"5a483e5cc0139b3023a22335a3255b962ea55fbd","datavalue":{"value":"journals/jcss/ImpagliazzoPZ01","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1604206$BD4AB219-12BD-42D3-BA5A-72658571DE98","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a8b308bf65c969dbce03437cfdf931b07768e3c","datavalue":{"value":{"entity-type":"item","numeric-id":2875150,"id":"Q2875150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"032acea0b6f2fae04e60622d85fb9a22f561feb1","datavalue":{"value":{"amount":"+0.8184396624565125","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":"Q1604206$9822885E-2E01-442B-8591-0AD1451C8561","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1c2a4a52a974f465051dfaad6d36ce2d5859a91","datavalue":{"value":{"entity-type":"item","numeric-id":4962605,"id":"Q4962605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cda748fa07ab87ca8890cb31c816df6b976ef830","datavalue":{"value":{"amount":"+0.8175631761550903","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":"Q1604206$8A87C979-D16E-4FAC-9A82-1FC4494B2FF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"755bb9e2da3e04a3fdd2a172851bfa20892491a7","datavalue":{"value":{"entity-type":"item","numeric-id":5943094,"id":"Q5943094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b65dc5bb75f47e5a4351e39e570f7f2eaed4c3a2","datavalue":{"value":{"amount":"+0.8039827346801758","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":"Q1604206$A21CD87A-E31D-4941-AD8C-C35E1AB40FA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73031b6c517a4cb27504c670a466ea4b9c51c02f","datavalue":{"value":{"entity-type":"item","numeric-id":340559,"id":"Q340559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a07915d9595a3cc908c3722de2ac79553023026d","datavalue":{"value":{"amount":"+0.7963824272155762","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":"Q1604206$BB8B30D1-A304-4D7A-B9EF-3EF7B9C79747","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92df6d2cb4d8b7b9b91dcaa2517c6f2c02c5f933","datavalue":{"value":{"entity-type":"item","numeric-id":3612463,"id":"Q3612463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc7ab2d10dd25340606673f3a26253aa828cb99c","datavalue":{"value":{"amount":"+0.7907512187957764","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":"Q1604206$14EDC569-17E9-4A38-88A8-2B0F3F7D46DD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Which problems have strongly exponential complexity?","badges":[]}}}}}