{"entities":{"Q1107322":{"pageid":1118071,"ns":120,"title":"Item:Q1107322","lastrevid":49197337,"modified":"2026-01-06T18:13:36Z","type":"item","id":"Q1107322","labels":{"en":{"language":"en","value":"Models of lower-bounds proofs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4064492"}},"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":"Q1107322$F747DBED-1129-453F-ABF1-6EBFC2366832","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7959acecc6f9fc71749c549aec1f51e2a5d7bf0f","datavalue":{"value":{"text":"Models of lower-bounds proofs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1107322$66F0D404-1CBA-47AB-8E5A-574115C5674E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"85c0079f75563c143604c2fbfb17774b30f6f354","datavalue":{"value":"0652.68061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107322$5DB49F2D-AA9F-4340-A3EE-9AF64ABD6289","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7ab595aa7410e11925de3d9ee0f5b91e1e6ec581","datavalue":{"value":"10.1016/0304-3975(87)90110-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107322$105D1672-3AB1-4E89-A4CB-F903F0F878FD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"afab7db2c8c0703d7cbdb91f92f1ebc1e9335a11","datavalue":{"value":{"entity-type":"item","numeric-id":1107321,"id":"Q1107321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107322$DF791C94-38CB-49D7-88A6-B7DB5FBA8745","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":"Q1107322$062C1E44-2AB7-45B7-B871-0753C5BB842E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1107322$E7F9EE4C-5D5C-483E-B795-F8F36840A775","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"45cb54164a1983ac228b942019ec3154eb68914e","datavalue":{"value":"Two models of widely applicable lower bound proofs are introduced. They allow to associate a set \\({\\mathcal F}\\) of Boolean functions with every such a proof. The complexity of functions from \\({\\mathcal F}\\) is suggested as a criterion distinguishing ``effective lower bounds'' from ``noneffective'' ones. It is shown that proofs with \\({\\mathcal F}\\) containing functions of n variables with the size complexity at most s(n) cannot produce a lower bound exceeding \\(O(s(n)\\cdot (n+s(n)\\cdot \\log s(n)))\\). In all known lower bound proofs it is \\(s(n)=O(n)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107322$E023DE71-A590-4AE2-B7E5-49BCCB8A06C6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107322$FB9D9CE7-C4E8-4ABA-8CF9-B3797934FF28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ece9b879f80d96e2a1d45b28bdcc8cfa6b01861e","datavalue":{"value":"03F20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107322$23CA090B-2A97-4D3C-A718-3241A854049C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"030bdcf6a53f2af8d82183608085bc4de7ef8734","datavalue":{"value":"4064492","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107322$EE511235-34E7-416A-A1CE-EB4CC96E227B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eebe0b75099119d5ed0fd55b0d34a9fc478c66eb","datavalue":{"value":"Boolean complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107322$3D5E4C3E-8E54-47F0-874D-59AF0BFE9863","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3dd7b55af63a54b6c14a2c438783858aa290223e","datavalue":{"value":"lower bound proofs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107322$FD72FAFD-067E-4A8F-B651-B8E838E9F689","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb5a830579b475e59eaac799be7398a9142f423b","datavalue":{"value":"Boolean functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107322$54103403-9A31-4B96-BFF6-93AB0A85985D","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":"Q1107322$503C64FF-BD4E-45EA-82C2-88B6177A78AE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a4f1172263bb5bc4c7037e19d126103156ecb878","datavalue":{"value":"https://doi.org/10.1016/0304-3975(87)90110-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1107322$877EEC22-0B51-4397-B818-46B964A54594","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"19f2376a8717bd4975b11a5a8bf492a6eb6ef133","datavalue":{"value":"W1986229957","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107322$7E93FDDF-8D7A-41AB-B862-585D9755B95D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"58af9a438ca79f17e01d4568050919b82873e432","datavalue":{"value":{"entity-type":"item","numeric-id":794625,"id":"Q794625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107322$19C294A4-3159-435B-89D0-E0005AA2D380","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b68ccb109d96060d1bc92f7834505a42c0f66e9","datavalue":{"value":{"entity-type":"item","numeric-id":5567891,"id":"Q5567891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107322$7F3B14BC-88D9-44F9-A401-0F133C62F2D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"098af7a9c815eb0fb6c191035a2e96fcc2eb7329","datavalue":{"value":{"entity-type":"item","numeric-id":4692286,"id":"Q4692286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107322$18ED9E33-DA53-4D6B-BAE1-92056495D203","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bdf68a334d2f611e409ac810a6dd0c524d53a39","datavalue":{"value":{"entity-type":"item","numeric-id":3713999,"id":"Q3713999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107322$1D3E187A-D0A1-424D-A0DD-303A36D8C9F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36b6a61f0791a1ff9903f693bedb57a39ab7a706","datavalue":{"value":{"entity-type":"item","numeric-id":3691585,"id":"Q3691585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107322$7F01B18E-88B4-47AA-85AB-640DB8E7DDB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e266c332c8c722703a0d32ad33eb1d65fa4f734","datavalue":{"value":{"entity-type":"item","numeric-id":4131019,"id":"Q4131019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107322$DDF68139-0F86-4779-8389-F219E66725BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0be07caf9e848c641ba91e5af6add50499139e44","datavalue":{"value":{"entity-type":"item","numeric-id":5684582,"id":"Q5684582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107322$775D0394-936D-4402-B4B5-AD0D905EEE31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c43b242e8d2a6febe28b4e1a41898561ecb7a1a8","datavalue":{"value":{"entity-type":"item","numeric-id":4138141,"id":"Q4138141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107322$BC9085C4-0EE0-4FBF-95F5-5DCF0A2122F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cebd8eb2f5a77bc77e1ec5c5bf27647529b62ed","datavalue":{"value":{"entity-type":"item","numeric-id":1228356,"id":"Q1228356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107322$4D942F51-2552-4A96-8DD8-B3C451C5E20E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c7753b2c0a0136d36e0e6594c32ff134628ef23","datavalue":{"value":{"entity-type":"item","numeric-id":4146674,"id":"Q4146674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107322$87A7343E-B2D5-411D-B907-E29B1C78B0A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ea036af6b978e5cc70c3a09e0db8705cf203783","datavalue":{"value":{"entity-type":"item","numeric-id":4140882,"id":"Q4140882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107322$DF289060-A0A5-4FF7-A615-992F462D25C9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"260d628c70d0e9213ad4b7ffeb7248fa9961e620","datavalue":{"value":{"entity-type":"item","numeric-id":4002028,"id":"Q4002028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75b8f19363a867cfbf1d6aad1f318829fa2086e8","datavalue":{"value":{"amount":"+0.8035585880279541","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":"Q1107322$C4D0737D-1918-42D8-B8AB-EDB971542286","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8884fca1e9d12667d29e6a056ca82dc313236dbc","datavalue":{"value":{"entity-type":"item","numeric-id":5890841,"id":"Q5890841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"faaf62b3bee5a1a52138223d2212e950af5b18bc","datavalue":{"value":{"amount":"+0.8024388551712036","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":"Q1107322$10205294-F362-402D-B00C-629D41E72F4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a99656fa8549640caed6056adc1c4975be0aeefc","datavalue":{"value":{"entity-type":"item","numeric-id":5906823,"id":"Q5906823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9bb5fd351087285119eb753116482c27bd694d5","datavalue":{"value":{"amount":"+0.7997769713401794","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":"Q1107322$45637FF4-095C-4F81-94C1-74235D7DC628","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0074d3e1482d2291b46ba2d08f3e736061ae14f7","datavalue":{"value":{"entity-type":"item","numeric-id":4029623,"id":"Q4029623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39fa6961fd9151f72c895fd00d04a5e81dfe38ff","datavalue":{"value":{"amount":"+0.7970470190048218","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":"Q1107322$9770679A-185F-4401-AC1A-07A56A809837","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3ee24e5941a980d341edec213329522344ee401","datavalue":{"value":{"entity-type":"item","numeric-id":4818823,"id":"Q4818823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39fa6961fd9151f72c895fd00d04a5e81dfe38ff","datavalue":{"value":{"amount":"+0.7970470190048218","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":"Q1107322$C8605848-94A5-49CF-8691-88FDA7CB0AF4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1107322","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1107322"}}}}}