{"entities":{"Q2848219":{"pageid":2858939,"ns":120,"title":"Item:Q2848219","lastrevid":51833162,"modified":"2026-01-20T06:39:20Z","type":"item","id":"Q2848219","labels":{"en":{"language":"en","value":"Improving exhaustive search implies superpolynomial lower bounds"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6211602"}},"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":"Q2848219$FF5AF753-D304-4F9F-989A-8C9AF730DB53","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"25323d25502bc59cccbdc51bacd2fbd0817d8218","datavalue":{"value":"1275.68071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848219$D16A53B3-032A-4186-95EF-72C3D00A6859","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"81cb6b362a96e985f9cbbbfd11fa867641839301","datavalue":{"value":"10.1137/10080703X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848219$BF90602D-1570-4A00-BA4C-F1CE6F24DF4B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c2a1c45d0f0997786c62faf9f7fcd603424632e8","datavalue":{"value":{"entity-type":"item","numeric-id":84798,"id":"Q84798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2848219$120CAFCA-C05D-4F00-96EA-B6C2F9EFB89F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"68e9606d4f4e53be9a37b58bd23167a8b2b94aea","datavalue":{"value":{"time":"+2013-09-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2848219$A28539E2-2115-4308-B56C-BA0EFC92E9CA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848219$A86441B2-8E0F-4632-8D20-1248804EB96E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848219$FDE47BD3-715B-47E6-9877-957443319E61","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"44ac3c6c0af24efcfcd2c8cd8639944b71e57e5d","datavalue":{"value":"6211602","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848219$5C7A14E8-85F0-4C88-8148-07B397DBDAE2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q2848219$F83BE7C1-B58C-49C9-B1C9-2867900BC824","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ca3de341fd958bc0dc5a652db63949843e8dc47","datavalue":{"value":"improved exponential algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2848219$C453E8AE-8D8A-49A5-916F-A4D304B53DCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f3f05553a5308936a7205a0d3afccb9b8d271916","datavalue":{"value":"exact algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2848219$B1C25C56-815B-42F7-8B04-C84BA4389456","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea32b2b549fd24419a857c0b59d8e23ba30ff6f8","datavalue":{"value":"time-space trade-offs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2848219$80BE7762-9D35-4078-B90F-9D0C5789092B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f0cb341ca7876bc8468eee4ea8e9008984980e7","datavalue":{"value":"circuit complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2848219$DF2F247E-5914-45B5-B07E-4BB0F8946C90","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":"Q2848219$F84D1CFC-B9BD-4EFF-8FF9-156E8DDF5E73","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":"Q2848219$34B0E350-00F3-4743-AE1E-90FA9694E10E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0e45b0fd9ac37d1d75293ed364962624aabb8ece","datavalue":{"value":"https://doi.org/10.1137/10080703x","type":"string"},"datatype":"url"},"type":"statement","id":"Q2848219$39226981-0580-41D7-9AE0-8DAD70EDC7C9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ba064119d575703cf63d4ce44a0e8643f6172a07","datavalue":{"value":"W2004130530","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848219$97B1ED42-DC35-4F84-9FB5-140FE0737105","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":"Q2848219$72013CCA-3CE9-4A84-AEC4-967B6A709DF3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"72e0ee399923e1800fbe8589bd16536693abbcc5","datavalue":{"value":{"entity-type":"item","numeric-id":2875149,"id":"Q2875149"},"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":"Q2848219$58DD140D-88C1-46D4-8CA1-2E3BC158FF3E","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":"cbe400212d004af1033d9646f14791f362b382fd","datavalue":{"value":{"amount":"+0.7340420484542847","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":"Q2848219$A259A97F-BEB1-481F-A026-F23BEA65580D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4fd3bcf874ba2125cc26179a803bc97afdb12c4d","datavalue":{"value":{"entity-type":"item","numeric-id":4036579,"id":"Q4036579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cbe400212d004af1033d9646f14791f362b382fd","datavalue":{"value":{"amount":"+0.7340420484542847","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":"Q2848219$B80AE8E9-9F4A-44BA-ADBE-8B6B0242EAB3","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":"90966ebb247fcd15e03cd07eddcc432e4d4c8670","datavalue":{"value":{"amount":"+0.7239130139350891","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":"Q2848219$41FA1DC7-A394-4D4B-9D8E-2AA8361510DC","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":"b75b4fdaea2d4da0991b6755b69678b3b073bc68","datavalue":{"value":{"amount":"+0.7167717814445496","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":"Q2848219$CE4CA2D6-9832-4243-AF39-3E6F9D6EACAA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2848219","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2848219"}}}}}