{"entities":{"Q1575258":{"pageid":1585998,"ns":120,"title":"Item:Q1575258","lastrevid":72229443,"modified":"2026-04-14T03:29:40Z","type":"item","id":"Q1575258","labels":{"en":{"language":"en","value":"A read-once lower bound and a \\((1,+k)\\)-hierarchy for branching programs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1493203"}},"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":"Q1575258$F96581F8-16BB-448C-A393-9BEA35C1F9AD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"987d3983ac1bce64d0b73d98ba9949ce0dadd579","datavalue":{"value":{"text":"A read-once lower bound and a \\((1,+k)\\)-hierarchy for branching programs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1575258$536D171C-2471-4DBC-9C40-C7BD16E68B29","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a7510cdb6f859ef7a43a1699c83e103c570d3705","datavalue":{"value":"0947.68056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575258$4CC0A41D-9CA3-4DC0-AAE2-CD40053D36CE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e7b758a411bcdf9678ed1821d61db0738c023085","datavalue":{"value":"10.1016/S0304-3975(98)00219-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575258$77D29461-FE38-4748-A93F-60C5589F1E94","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":"Q1575258$FE96AECB-DC15-480C-AFC9-07BCFE51A51E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b3a497233c3b9babc42d370358782cbff338a7a1","datavalue":{"value":{"time":"+2000-08-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1575258$0CD60096-4C8C-454C-8BE5-E87A5DB63364","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f78111dd89e59ecba4a595c906c66eab62024705","datavalue":{"value":"Branching programs (b.p.'s) or decision diagrams are a general graph-based model of sequential computation. The b.p.'s of polynomial size are a nonuniform counterpart of LOG. Lower bounds for different kinds of restricted b.p.'s are intensively investigated. An important restriction are the so-called \\(k\\)-b.p.'s, where each computation reads each input variable at most \\(k\\) times. Although exponential lower bounds have been proven for syntactic \\(k\\)-b.p.'s, this is not true for general (nonsyntactic) \\(k\\)-b.p.'s, even for \\(k=2\\). Therefore, the so-called \\((1,+k)\\)-b.p.'s are investigated. For some explicit functions, exponential lower bounds for (1,+k)-b.p.'s are known. We prove that the hierarchy of \\((1,+k)\\)-b.p.'s w.r.t. \\(k\\) is strict. More exactly, we present (multipointer) functions \\(f_{n,k}\\) which are polynomially easy for \\((1,+k)\\)-b.p.'s, but exponentially hard for \\((1,+(k-1))\\)-b.p.'s for \\(k\\leqslant \\frac 12n^{1/6}/\\log^{1/3}n\\). This is a generalization of a similar result of \\textit{D. Sieling} [J. Comput. Syst. Sci. 53, No.~1, 79-87, Art. No.~0050 (1996; Zbl 0859.68027)] for syntactic \\((1,+k)\\)-branching programs. As a by-product, we prove a lower bound of \\(2^{n-3\\sqrt n}\\) for an explicit (pointer) function in P.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1575258$C701E71E-1D79-4D01-AA33-67E60FFF99DC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575258$85745AE0-17B3-458E-A66E-EE17D1136B3E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4ef9c5ec5f18bdd9b4f49a9463d01f772fd39d00","datavalue":{"value":"1493203","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575258$55E8BAE9-9C91-4B2B-94AE-2A7996B268E8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb5a830579b475e59eaac799be7398a9142f423b","datavalue":{"value":"Boolean functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1575258$078E7637-5031-4C38-B32C-7E1DC4930A03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec24897927a0742784fae89aed9a922bc2a81fec","datavalue":{"value":"branching programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1575258$41E8F5FF-CD6A-41AE-A49A-108FEE234B99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q1575258$B2CA793D-A75C-4788-A44A-5D44CA5AD005","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3130e87f1749c59ee4d0e395d449a1e09007fc09","datavalue":{"value":{"entity-type":"item","numeric-id":278738,"id":"Q278738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575258$9837C4E2-2A51-4256-A760-EE72B65C5E30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ac194c8415729c0b069bd70e642b567c974b0dcf","datavalue":{"value":{"entity-type":"item","numeric-id":593779,"id":"Q593779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575258$9348656A-1D2E-4647-AA0B-F3086CEDADD2","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":"Q1575258$7657FAB8-7940-45F5-B63A-DA684D4BB6F3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d4dad721c7b2eb217b7e2ac4fb117895325d0e3","datavalue":{"value":{"entity-type":"item","numeric-id":4571952,"id":"Q4571952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575258$999EE0FF-A529-44C0-9E5A-39DFB872032C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89c68861450e9d42f2d00abacda154e9249e5a0b","datavalue":{"value":{"entity-type":"item","numeric-id":1912283,"id":"Q1912283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575258$3243DDFD-3C17-4096-A1C2-556015300692","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"460a7d56c9002563be5b888d0342c1492ebca797","datavalue":{"value":{"entity-type":"item","numeric-id":4938624,"id":"Q4938624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575258$F58107C7-160C-4D18-8764-3D006BBAE3D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5c31e8d2807d1ce4f8ab6661996ea0ee3ab237a","datavalue":{"value":{"entity-type":"item","numeric-id":1107323,"id":"Q1107323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575258$0FCB2251-4036-40B0-8D04-40539C639E00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f4150d4584eafb8457c578c72e61f86894bc805","datavalue":{"value":{"entity-type":"item","numeric-id":2366719,"id":"Q2366719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575258$660855AB-3FFF-4018-A200-39436012BB90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50324ccb6206134f253ce476b8660b15930be48f","datavalue":{"value":{"entity-type":"item","numeric-id":673087,"id":"Q673087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575258$C2508190-5A94-4149-9DA8-F7B9C2FDE728","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e65945bbae4ba0f8c193c21fe759af9d718b474","datavalue":{"value":{"entity-type":"item","numeric-id":4314567,"id":"Q4314567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575258$3579B05E-0A2E-43D6-B615-944323136B11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f79e196504a8abce7f5d12820a1bf92cd3de6085","datavalue":{"value":{"entity-type":"item","numeric-id":3694708,"id":"Q3694708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575258$3E7905B1-2200-4A2E-B7E8-451EAD6552CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15121ed03afeca51fa9da12f2f9ffc129110a275","datavalue":{"value":{"entity-type":"item","numeric-id":287023,"id":"Q287023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575258$AE80D08D-202D-4CD7-A4B8-4A0DDC064FA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35b4530d636dec7ea0f4404c37204b3c46ebc9d0","datavalue":{"value":{"entity-type":"item","numeric-id":1109754,"id":"Q1109754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575258$02125C4A-6282-4DB5-953D-07BFC35FB3B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68c959b34df4e4ce5a3dcb3c44885ef547d04acf","datavalue":{"value":{"entity-type":"item","numeric-id":4362278,"id":"Q4362278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575258$34D9AC59-3A61-4D88-8A1B-9D23EEAA4BCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dce5067a293418eb4f750633f75fb90d4429ba46","datavalue":{"value":{"entity-type":"item","numeric-id":1130185,"id":"Q1130185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575258$FA2E1221-F905-4573-A8E6-C38736147EC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33195a409f6981ebf2d25011b284b858dec71b8f","datavalue":{"value":{"entity-type":"item","numeric-id":3783566,"id":"Q3783566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575258$61816C0D-3D66-4258-9672-C9277FC83B73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a13f2d8e6154350b4fa2479fd6e4337c336b0fd","datavalue":{"value":{"entity-type":"item","numeric-id":3364203,"id":"Q3364203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575258$9596E7D6-E137-4E0A-A75A-1CEA117372D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c91f03e27e539a51858d50e5d9fd1b8dac3af73d","datavalue":{"value":{"entity-type":"item","numeric-id":4234058,"id":"Q4234058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575258$5C075ED2-4325-41F1-9522-021EC9D3BA3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad00a83b5d740d9489736b8014faafa0c722caaa","datavalue":{"value":{"entity-type":"item","numeric-id":3248054,"id":"Q3248054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575258$D68DE619-8BD9-4D99-8D1D-60D7DFE920F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a58f4abc51a121daf7d02df4385433675626496e","datavalue":{"value":{"entity-type":"item","numeric-id":1392030,"id":"Q1392030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575258$DE308ABA-BF4A-4693-8C49-5DC899E011FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58a3bfa7558c7d57431714d80b8f074aee550cdb","datavalue":{"value":{"entity-type":"item","numeric-id":1816743,"id":"Q1816743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575258$C1F695A5-3187-45BB-AF1F-53271C5DDF90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0962521a64e4c207ee4c6274955735371b352ef8","datavalue":{"value":{"entity-type":"item","numeric-id":4287364,"id":"Q4287364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575258$E5C74539-A494-4790-B114-CC7A83530383","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b82601988f1a6239764f109a2a1130fb98712c4","datavalue":{"value":{"entity-type":"item","numeric-id":3798243,"id":"Q3798243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575258$05F3B70E-A493-4C96-B668-F9BA311AFF75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21bc7c146c515de56380f9786cb8389fb225ca92","datavalue":{"value":{"entity-type":"item","numeric-id":3347300,"id":"Q3347300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575258$7955CC1F-7551-418C-AB15-0D7EAF9A6DC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e58af1a26c64d46d28f7e31549127be05f9a0df3","datavalue":{"value":{"entity-type":"item","numeric-id":3569022,"id":"Q3569022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575258$09BA7EEA-5B29-47D9-89BA-46D7ABF04E00","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"8a56867bb9be5eea282d874e8ccb3a31467b607d","datavalue":{"value":"Q127725420","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575258$9B902BB9-070D-4108-B196-92480FFDFADA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"730ca157dc900b146086fc761007ed7c94adcedb","datavalue":{"value":{"entity-type":"item","numeric-id":4699324,"id":"Q4699324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"986a0e5ce7e82bb4fa317107ed84f01e326587a5","datavalue":{"value":{"amount":"+0.9516286849975586","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":"Q1575258$50E1B2C7-6D81-4ED2-AF2B-E376B4297819","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8669cbcf37c61d9bffb64756c4a730e7f95140a0","datavalue":{"value":{"entity-type":"item","numeric-id":1816743,"id":"Q1816743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"378bd6a2bfeacd88d4159a71730939d61adfb35d","datavalue":{"value":{"amount":"+0.8915150761604309","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":"Q1575258$91CE771E-8F1D-4BB6-849B-504B7FD747E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2051f95e319f1309481c420d048c4b62ebbe7566","datavalue":{"value":{"entity-type":"item","numeric-id":4736860,"id":"Q4736860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30645ae860a5c7179ad218da277693b1a65abb0b","datavalue":{"value":{"amount":"+0.8616151809692383","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":"Q1575258$AF53D4E1-87E8-4EA6-8C47-5FD125279AAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"985b1b1cabac17114dd5628e8bbe5467101a10da","datavalue":{"value":{"entity-type":"item","numeric-id":1392030,"id":"Q1392030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a97da6e0372b64bfd570a7ec0800ded023539553","datavalue":{"value":{"amount":"+0.8554978370666504","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":"Q1575258$EAAC3195-1873-44A4-8768-AFA913700AEB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A read-once lower bound and a \\((1,+k)\\)-hierarchy for branching programs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_read-once_lower_bound_and_a_%5C((1,%2Bk)%5C)-hierarchy_for_branching_programs"}}}}}