{"entities":{"Q2875149":{"pageid":2885869,"ns":120,"title":"Item:Q2875149","lastrevid":52065230,"modified":"2026-01-20T21:04:18Z","type":"item","id":"Q2875149","labels":{"en":{"language":"en","value":"Improving exhaustive search implies superpolynomial lower bounds"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6330062"}},"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":"Q2875149$EE50C8E0-39FC-4EA3-9387-AB2319381083","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"aef7f89abfa768f34854707fdc9da8772d9ee7f2","datavalue":{"value":{"text":"Improving exhaustive search implies superpolynomial lower bounds","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2875149$75EBF9E7-1F2D-4DDD-9855-CDF9A34D8288","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0bda828317446b583005612a6ee6c53a45789d25","datavalue":{"value":"1293.68177","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875149$DACF134B-34BF-42F1-88DF-6D3EFE27659D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c38f25e456d2352735578131c9ce3791b00a2257","datavalue":{"value":"10.1145/1806689.1806723","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875149$F9352C8E-E3F1-40D9-87A4-E9E0B030B94D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"857e6d765dc12abc2ea24a145570b777b4cfba51","datavalue":{"value":{"entity-type":"item","numeric-id":2875127,"id":"Q2875127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2875149$1AD9036D-BB7B-43C0-9FEE-518E02A34F3E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f80e145b44ef7aa11a9e241ede63c58486ab29d7","datavalue":{"value":{"time":"+2014-08-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2875149$552B1167-A2FA-4EE5-ACA0-C18941592F99","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875149$40CA8539-0E8A-4B7A-8EFF-0DA8AA44C61F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875149$3398AAFB-C710-4E8A-96A6-98A30CF07C77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875149$1104649E-B062-4C79-A57F-6546A639F26E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d75b5a2d8be1822fded5a4c400e217df3632fc13","datavalue":{"value":"6330062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875149$2559F73C-2AC5-479B-A370-3A1D3AF95035","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f3f05553a5308936a7205a0d3afccb9b8d271916","datavalue":{"value":"exact algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2875149$375118C5-9FD6-47DE-BF76-A68A357025E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ca3de341fd958bc0dc5a652db63949843e8dc47","datavalue":{"value":"improved exponential algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2875149$D4A16108-5B51-4FB2-AF01-262673BD4098","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q2875149$93FA754C-E214-4398-B498-7FB5F89D9510","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6bf5e86d34b629e124b4bc7a75dd155da8e3cd8d","datavalue":{"value":"time-space tradeoffs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2875149$9724F746-51A2-4F84-A8AF-58EC6200C4EE","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"904cf9d7e1ce38a501c0fe9b3331295005061895","datavalue":{"value":"Q57568006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875149$834D642F-9735-459B-B102-B30E41608F3E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"78a3ebf267830b34bb8ced5ebe00bd1ba645205f","datavalue":{"value":{"entity-type":"item","numeric-id":937200,"id":"Q937200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2875149$596A5EED-81D9-4E2D-B4CC-73FFA5DEBAF2","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":"Q2875149$4D008D1E-79A8-40D1-8E87-990775F2EF2C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3432b5f7c31bcf12f5cf73f2b7d0997fbbd3562b","datavalue":{"value":"https://doi.org/10.1145/1806689.1806723","type":"string"},"datatype":"url"},"type":"statement","id":"Q2875149$4DDD8E60-D1B9-406E-B7C3-35E2FBE41BC4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"76925233320699f5d1fd3feb320a12fd6fb93ab2","datavalue":{"value":"W2007121506","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875149$B603A1E8-309A-4092-95B5-7B0AE140DB0F","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"8338f7a3065cc579c64f966831b089eac3945645","datavalue":{"value":"conf/stoc/Williams10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2875149$B387FDCD-4430-4ACA-B751-A287598C278B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"764952e776986d8597038035a640b2b4cdc8c4e4","datavalue":{"value":{"entity-type":"item","numeric-id":2848219,"id":"Q2848219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb69de071cc9a7afafd4427ead15afd046c8d16d","datavalue":{"value":{"amount":"+0.9864749312400818","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":"Q2875149$3111FCB5-1A18-4AB8-BC34-2367D8B2FCF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb30208f77df467623f4ae5e8da6fd11a46bf8c0","datavalue":{"value":{"entity-type":"item","numeric-id":1604206,"id":"Q1604206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74c82570a2c6cbb47b0b2aef694db98e7a17ac6b","datavalue":{"value":{"amount":"+0.7532532215118408","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":"Q2875149$2A9E6647-82AD-4C3C-8367-77D6B3C598B3","rank":"normal"},{"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":"74c82570a2c6cbb47b0b2aef694db98e7a17ac6b","datavalue":{"value":{"amount":"+0.7532532215118408","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":"Q2875149$B2E21850-9A95-483B-A2B3-7439B65DDA78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5bf38cc888921590df143be54d6b97aac5f0ba8c","datavalue":{"value":{"entity-type":"item","numeric-id":4668733,"id":"Q4668733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1be9154af523ffffc17b14b2d1132e2934fe72c","datavalue":{"value":{"amount":"+0.7305815815925598","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":"Q2875149$F3F66AA2-8563-4AB3-8C13-4103DFDB6223","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5f126af51bb0406a718eeb65fff14b7bf10fdf5","datavalue":{"value":{"entity-type":"item","numeric-id":2460033,"id":"Q2460033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3f8f6eb64ceecbddb0888c465ae7d5df7122058","datavalue":{"value":{"amount":"+0.7267575263977051","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":"Q2875149$AB3A3E39-6843-4E4B-9032-1D8C9C33DF6C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2875149","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2875149"}}}}}