{"entities":{"Q1050255":{"pageid":1052103,"ns":120,"title":"Item:Q1050255","lastrevid":66628989,"modified":"2026-04-12T11:24:59Z","type":"item","id":"Q1050255","labels":{"en":{"language":"en","value":"Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3809332"}},"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":"Q1050255$B7199C27-3892-4042-9815-83BB64D48366","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b6ab5b89895a19f76f64bc1346330dbc44dd92f8","datavalue":{"value":{"text":"Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1050255$620EE5D2-F3C2-4D8A-BE8D-8476406E8BBD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"07cb529af0ea62d93bb008162587503e39a14364","datavalue":{"value":"0512.90076","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1050255$66AECECF-FE21-4FAC-B3B6-7CCD388C0C50","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b908120f98bb9a906b9731c159a9de42496b66eb","datavalue":{"value":"10.1007/BF02218439","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1050255$019E2F7F-2F6D-462F-B6AF-90A087E4012D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9aa4172a39bf9ec948c8d6eb790fa409bd68117f","datavalue":{"value":{"entity-type":"item","numeric-id":294883,"id":"Q294883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1050255$60915DCB-945A-4A0C-A84F-FE55E764DD4B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e560271c921b84b65a9b7f0d3fa6830623f8af8b","datavalue":{"value":{"entity-type":"item","numeric-id":188629,"id":"Q188629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1050255$D067F74A-73DB-4FF9-86EB-EFF989193B9E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1050255$A66E01FE-26DC-4834-9A40-1209B789E39E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1050255$E9B2DE4D-A51D-406A-B171-C03411A24774","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1050255$3BCE93EF-1C0D-4381-9001-055FD512ACE0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a640aaea46aee66efef39b4a84f157b759294e17","datavalue":{"value":"3809332","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1050255$E34200F9-68A9-4765-89AA-91795D5114DA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f7fd3250219cc2b332afbff67ab81c9f9d953b2","datavalue":{"value":"23, 181-192 (1983)","type":"string"},"datatype":"string"},"type":"statement","id":"Q1050255$5EA5C145-B869-4DEA-9C2F-7800240C2BD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb539388cb15cc8716b894ca26cb723f56f9ba4f","datavalue":{"value":"exponential lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q1050255$0F8472B9-A0E6-4B4F-AB45-1AE064A36CA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"20be995b98d9f837a38f5deb4fdf231843a599da","datavalue":{"value":"restricted linear decision tree model","type":"string"},"datatype":"string"},"type":"statement","id":"Q1050255$1C7028E7-9B87-472C-BF76-7C7F965928EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8de18497c4fa0b752b21eeb32d98975ca57c40f1","datavalue":{"value":"linear recognition problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1050255$9A4FCFF5-3D50-4D39-B96A-B71C5E45089A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"52ecb80d5e2a4cda0460078c43ba218b74ba8622","datavalue":{"value":"ternary comparisons","type":"string"},"datatype":"string"},"type":"statement","id":"Q1050255$D74B0380-6421-4BB4-BE81-251DDA137F65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f81c64e75a374899f45ad403a8d5e6c86c980d59","datavalue":{"value":"lower bounds on the number of comparisons","type":"string"},"datatype":"string"},"type":"statement","id":"Q1050255$89611E59-D0A9-4A5B-BD07-69037D12BBAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59aa9ec9e79231abd911346c3bc612bf68171f66","datavalue":{"value":"linear test functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1050255$C37B5E89-5EA7-4CE5-B142-85E23D6770D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1050255$C8A5171B-15D6-40A4-B6E1-FA8E3CDA5E04","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":"Q1050255$0EA7D994-5981-4C7F-A621-BA8F413661F1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"02dafaebadaa856d5013d925b7e550701ae99578","datavalue":{"value":{"entity-type":"item","numeric-id":1253918,"id":"Q1253918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1050255$49E71663-1BE8-4FB5-BD70-59486197ED8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a95be383f4814efc07c25732619c12742108f623","datavalue":{"value":{"entity-type":"item","numeric-id":1259164,"id":"Q1259164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1050255$4F4EEEBE-D52A-4E79-9202-3CFF6E690B1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb19f12b7c7c70b4050c076bf47c50f4b7b37bb1","datavalue":{"value":{"entity-type":"item","numeric-id":2265260,"id":"Q2265260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1050255$4B4B8D15-D993-405C-8734-F0E4063BB6F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"260e7e66fdf79381c9a7667ebc2df65dbfcd85a4","datavalue":{"value":{"entity-type":"item","numeric-id":3926036,"id":"Q3926036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1050255$24DBCDFC-4831-43FE-8E2B-A0D65647B483","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf851580ae91acae3bb4962517461ba598b1a7f0","datavalue":{"value":{"entity-type":"item","numeric-id":3893331,"id":"Q3893331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1050255$269F47BC-D30B-4630-8A83-7C315A277C14","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e8fd8ec740490b3d788ed138d9976e15868d2bbd","datavalue":{"value":"https://doi.org/10.1007/bf02218439","type":"string"},"datatype":"url"},"type":"statement","id":"Q1050255$B3BDEC9A-A725-4A3B-A60C-085D7D2F0B9F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5bbf5c5867485262118ea84c0efe30056c5388a8","datavalue":{"value":"W1975384529","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1050255$3FEEF465-D715-4C6E-AC4A-B99C81F1435C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Exponential_lower_bounds_for_some_NP-complete_problems_in_a_restricted_linear_decision_tree_model"}}}}}