{"entities":{"Q620964":{"pageid":622740,"ns":120,"title":"Item:Q620964","lastrevid":63117918,"modified":"2026-04-11T10:42:26Z","type":"item","id":"Q620964","labels":{"en":{"language":"en","value":"Speedup for natural problems and noncomputability"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5843655"}},"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":"Q620964$59EEBFBD-BCB4-44DB-96B8-F308C4C40C0E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"300b1d13dbd3d969d576904c377e5f54183b3d34","datavalue":{"value":{"text":"Speedup for natural problems and noncomputability","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q620964$782EEDCE-F530-4B48-A5C9-15E25EBA185C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7aacd5c8c762b4ceb55088d14c3b723c3f889f98","datavalue":{"value":"1206.68177","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q620964$8B3B2AC7-6B77-46DC-A125-239C5BAE6C70","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"56050a9ba2cb690fb09990770fc7eef08677e42f","datavalue":{"value":{"entity-type":"item","numeric-id":620963,"id":"Q620963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q620964$2EDCFE58-23C4-4881-9E22-6493B84E69D3","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":"Q620964$86793925-D313-4D4E-8138-829BBBD3CEEA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"90226e22c518bbf24899277aeaad1e3115bd0ee6","datavalue":{"value":{"time":"+2011-02-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q620964$8CB5E213-41A6-4EB0-92FF-D3503E2ECC68","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q620964$AB957C45-88B0-44FB-A662-55056402B5FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q620964$B8491B31-8D7A-403E-96D6-71E61DBCAA59","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"72034cde74f63243e949cc5fd79235a46f700fa4","datavalue":{"value":"5843655","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q620964$AF653688-51F7-4376-85DF-36DEE805995F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"adee8dbd2b97b8f8edf84564a782309afea3f9ac","datavalue":{"value":"speedability","type":"string"},"datatype":"string"},"type":"statement","id":"Q620964$74A79425-0B73-4055-AB18-55542D48A99A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"933d82890d47d834bf65eb8a14d7bb8b0fa1e0b0","datavalue":{"value":"superpolynomial speedup","type":"string"},"datatype":"string"},"type":"statement","id":"Q620964$F0B31AFC-71B6-4450-9790-B0B55EB14C25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"71d6316755aa4b60da79df35d2f47f228fd75565","datavalue":{"value":"coNP-complete language","type":"string"},"datatype":"string"},"type":"statement","id":"Q620964$A2A87000-B8E7-4800-B1BF-598134AE2613","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7e5c986c44cadba2608d15cdbdbd7fbd9525b6f9","datavalue":{"value":"propositional proof system","type":"string"},"datatype":"string"},"type":"statement","id":"Q620964$F5250B97-FBF3-4E0A-BA55-F7DE7F2B68BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc00012563a75ed0c7975e9c32d5f2d16f0982e3","datavalue":{"value":"optimal algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q620964$E1B0F3A2-4ECC-4E99-B891-817B0969F513","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":"Q620964$4CD1C408-5E84-40E6-85D9-4F9633A89A10","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c28597a12c8778f0640b97fa06ccf7d363cb5114","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2010.09.029","type":"string"},"datatype":"url"},"type":"statement","id":"Q620964$684D660A-9CEF-499D-928B-767562757180","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cef2900354f2497d46124cb302f90a9de747c335","datavalue":{"value":"W2057550516","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q620964$68397D76-2F93-46E3-A73A-136EB8AA3AB2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea45854da7df1d421d45b7aeb6b91b2908960cc1","datavalue":{"value":{"entity-type":"item","numeric-id":5537605,"id":"Q5537605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q620964$946F2DFA-4B40-4908-947C-DD0AD8D9CDE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"121c519d392a5a20e66eeb2da987db2722b6b07d","datavalue":{"value":{"entity-type":"item","numeric-id":3586043,"id":"Q3586043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q620964$E39FF166-2E9D-455B-AA06-47B32A23047B","rank":"normal"},{"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":"Q620964$79F484C6-E813-41F4-990B-7D95EAE4529D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"185812f4a394f61052aeca3705caa191a7cb923b","datavalue":{"value":{"entity-type":"item","numeric-id":3947117,"id":"Q3947117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q620964$49210DB9-D606-41FF-B035-E9D5AF8FF456","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"030786d5842049ba190b65afb6363bf3c2a4868b","datavalue":{"value":{"entity-type":"item","numeric-id":3113771,"id":"Q3113771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q620964$D535C2B4-CB17-49C1-AE66-FD5BA36FF58F","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":"Q620964$F4BB8809-2502-4AC4-8867-F71A6B055BDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbb6ffdc2da3f7f9fdafbed4d441b6ee26762fc8","datavalue":{"value":{"entity-type":"item","numeric-id":4472459,"id":"Q4472459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q620964$8D0F0491-EE3B-4C5D-8452-1EF4239B482B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25f4a86512e0f02bf82877dbb62313fcd7fe9ed1","datavalue":{"value":{"entity-type":"item","numeric-id":3472096,"id":"Q3472096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q620964$0824148E-C1DD-461B-9ACC-A84AC20CBE33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0d208916c9d05809760edbf98e4029e5f6fb13b","datavalue":{"value":{"entity-type":"item","numeric-id":5663367,"id":"Q5663367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q620964$78B46A28-D625-4913-858E-BFCDB9AB63E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18b24565061934ac02802de962f2d86779356d08","datavalue":{"value":{"entity-type":"item","numeric-id":3396633,"id":"Q3396633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q620964$AB4224A1-D106-4AAF-AC51-79E5A3B717C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aad5682a5deae9c22ad0d31344f3d9f95de62518","datavalue":{"value":{"entity-type":"item","numeric-id":799337,"id":"Q799337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q620964$685AA2C4-6113-46AD-85B7-E8D27569FA6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48d028816aa1136bcbd0ad9e470978d4676a90bc","datavalue":{"value":{"entity-type":"item","numeric-id":4067076,"id":"Q4067076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q620964$E2041FC7-FDDA-41A0-861C-2B7850DA363E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"654940ff1f196f83f0790b2730c6b8ece06265b3","datavalue":{"value":"10.1016/J.TCS.2010.09.029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q620964$18CE86EC-B90A-45C8-A619-59942DD4FF41","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e37fab5e2f150bba846c33ad819a72d23cd5bfc2","datavalue":{"value":{"entity-type":"item","numeric-id":3545216,"id":"Q3545216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"039a89a29ac5382ff78ef32faf8b977705f184f6","datavalue":{"value":{"amount":"+0.85845643","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q620964$9550FD3E-96FB-4660-83B9-8C0200B214CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"644072da40c317873cbcc6ec4dadca8155fd1795","datavalue":{"value":{"entity-type":"item","numeric-id":5425350,"id":"Q5425350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71122b5b9e6f37764c4b25899ba85fe835131980","datavalue":{"value":{"amount":"+0.8488645","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q620964$648CBF52-7E59-4C6D-8F43-7CE21B158C28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7048ae64d2e5ffb634c12dd26d2f587ff349dc2","datavalue":{"value":{"entity-type":"item","numeric-id":804293,"id":"Q804293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8fc344f92f2d95d17d6fa14a947061fd20eb3253","datavalue":{"value":{"amount":"+0.842547","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q620964$64CF1C35-0995-433F-8DA2-D159CE610502","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c6455cfd586776ee21d184fed6f0eb448e35772","datavalue":{"value":{"entity-type":"item","numeric-id":2841287,"id":"Q2841287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ee23c8c165b80d5a57d868de92125619e631e06","datavalue":{"value":{"amount":"+0.8423137","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q620964$A9A2A55E-8F63-4C6E-8AEC-5E2450019FEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"719f8e257887d49a6401e1578ea8a0d4166b0dc5","datavalue":{"value":{"entity-type":"item","numeric-id":4218858,"id":"Q4218858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f63db0ad011b6cb0207267e7a4b8bbedabc79274","datavalue":{"value":{"amount":"+0.8406481","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q620964$5105C479-2893-4903-B0AD-2FF3BDC95CAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8f0eb3cba87e0463661e74a8946872285c15ca0","datavalue":{"value":{"entity-type":"item","numeric-id":1434372,"id":"Q1434372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"96a1c3394843c8bb9c80bb3f92feccdfb5e89de1","datavalue":{"value":{"amount":"+0.83904874","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q620964$1A54060B-3CAD-4920-9665-42B14F837911","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ed285be88e317547995d12df6813958ac92a437","datavalue":{"value":{"entity-type":"item","numeric-id":1853491,"id":"Q1853491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3456f87b6de8d6faf10ea53831fa913f1b9d4197","datavalue":{"value":{"amount":"+0.8389559","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q620964$90DB078D-81E6-4578-B2D4-21AE1F4DDE1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44401f01c01f6424d3f834ba07ab4903d9e28e18","datavalue":{"value":{"entity-type":"item","numeric-id":1098635,"id":"Q1098635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be861d18e6a2c1db4ad832adee6723e5ab1cece0","datavalue":{"value":{"amount":"+0.8385571","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q620964$327A341F-3480-4C87-93E4-BDF6C36645D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"643c590e76af5a95a93620d58faa8b905ef8c3d0","datavalue":{"value":{"entity-type":"item","numeric-id":1179219,"id":"Q1179219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47470eb3e71abdb31b0b1ee55309ac96a62f664a","datavalue":{"value":{"amount":"+0.8384463","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q620964$8B0A2192-3E8D-419F-97F7-EA408F7AF0E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6577e517fa47c352b13599bd4731b9d816a11c06","datavalue":{"value":{"entity-type":"item","numeric-id":3995973,"id":"Q3995973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3894e5e7231abc95e398b310df6d44d712a408e1","datavalue":{"value":{"amount":"+0.83743703","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q620964$2C68D9B9-66D4-436D-BF8E-52CB94F0A279","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Speedup for natural problems and noncomputability","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Speedup_for_natural_problems_and_noncomputability"}}}}}