{"entities":{"Q1854567":{"pageid":1865309,"ns":120,"title":"Item:Q1854567","lastrevid":73667289,"modified":"2026-04-14T16:50:53Z","type":"item","id":"Q1854567","labels":{"en":{"language":"en","value":"On the nonapproximability of Boolean functions by OBDDs and read-\\(k\\)-times branching programs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1853292"}},"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":"Q1854567$5F962285-38CD-43EB-953E-B2476A6FB5D9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"60fdcc93957e63137676aaf24cbb6d9c5479968c","datavalue":{"value":{"text":"On the nonapproximability of Boolean functions by OBDDs and read-\\(k\\)-times branching programs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1854567$7F8894AF-4678-438D-BD07-E7AA74AEF764","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"aa6038583f78ec4d561e8342cbfeed70f1b1151e","datavalue":{"value":"1012.68086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1854567$F733DC79-A715-4F60-9D1B-B623EC4DAD37","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a20c02e83754e20971084f9840112ad81e2d8c89","datavalue":{"value":"10.1016/S0890-5401(02)93174-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1854567$FB540C5A-EBD9-4262-8B56-8E35CACFCBFD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"be4ee1fbd4b7733cd16d69d04f0190aaf1da757e","datavalue":{"value":{"entity-type":"item","numeric-id":171934,"id":"Q171934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1854567$0A38E878-C75F-468A-8A45-EA66BFF48589","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a3c2a06ab8d1a3dc39a91ba24821db39c7fefb0b","datavalue":{"value":{"entity-type":"item","numeric-id":234347,"id":"Q234347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1854567$01C9A0C7-EEB6-4B8C-9593-8F8696F6839C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"00b3e57da97cbc00a7ce7385e258f05ae9a6ec6b","datavalue":{"value":{"entity-type":"item","numeric-id":171935,"id":"Q171935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1854567$2C467A81-E302-4B7E-810C-B861B8DF2096","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1854567$333C8494-470B-4A22-9407-EDBFF3CED208","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6a7e8d599a17c373ba2d71fc88b3043673b9f45a","datavalue":{"value":{"time":"+2003-01-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1854567$81017A8F-3D55-4019-B144-4C29A409084D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1854567$15663C06-193A-47A8-BDE8-C529CC9057EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cfe779e91fe9c53ee133568259955801965765ae","datavalue":{"value":"68T05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1854567$47C7472E-A389-458E-A525-6E0A48ACE2AA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"beab4f4bfa5e8c3c12c98ecb55c253286858026b","datavalue":{"value":"1853292","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1854567$BD606BFC-3812-4FDE-9607-FC31B5B16CCA","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":"Q1854567$4957F030-27EF-477D-9B1A-C796A3AF9ED0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cbcd3741298261fc84fe00c1eae6a707c88179c8","datavalue":{"value":{"entity-type":"item","numeric-id":2819593,"id":"Q2819593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1854567$220F8531-ADE4-48B9-9F34-8CBD7C1F6508","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb77facc02f21ad2f21d191c8d7a4263305b54d1","datavalue":{"value":{"entity-type":"item","numeric-id":1115606,"id":"Q1115606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1854567$B57245E6-2D54-4EAC-AE57-CFE744D3B3DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"586511571dad179f87075fc6c741113b4ab73514","datavalue":{"value":{"entity-type":"item","numeric-id":4542591,"id":"Q4542591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1854567$B11ECA73-0C51-4895-96DB-A799F1D4DFB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e829ea50318f576a76deefc5f66e35383fc7395","datavalue":{"value":{"entity-type":"item","numeric-id":1604208,"id":"Q1604208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1854567$4DA6770D-28B3-4BA0-AFA1-BCC8ADBEAB8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29c30f9f448fb1fd75a320e8b96473cbce649725","datavalue":{"value":{"entity-type":"item","numeric-id":3579215,"id":"Q3579215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1854567$FD68D1E1-A8AC-4E5C-B5BC-3592667D23D6","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":"Q1854567$5CD527EF-C425-46EC-8E54-4AB902A66C21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb831a926f4740f70cbc7d7c440aa3f25cfdd945","datavalue":{"value":{"entity-type":"item","numeric-id":1173954,"id":"Q1173954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1854567$7D07AF53-DC75-4C82-A0AB-811AEA8642CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57f481a492a07716c343ede4ef9f6626a82012b3","datavalue":{"value":{"entity-type":"item","numeric-id":4032302,"id":"Q4032302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1854567$0C2112A1-6D04-49AD-9351-E62079604F55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d70df7d2773c909e2985f0422310b699f58eb7ad","datavalue":{"value":{"entity-type":"item","numeric-id":1300607,"id":"Q1300607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1854567$1139FE29-7954-4C26-A46C-675DD9F58FAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ec4896edc35f1e12505542682c8c6b6145a21f0","datavalue":{"value":{"entity-type":"item","numeric-id":4875692,"id":"Q4875692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1854567$ADDB58CB-1F62-40A9-A940-04974750A15C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4304077c8e158fef029455f7fb0aedb68ee12a3","datavalue":{"value":{"entity-type":"item","numeric-id":5957726,"id":"Q5957726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1854567$2F085CED-2C44-4567-A9AF-FC481E411EEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ee9bdbd9786926088840fd488fe60b509eb451c","datavalue":{"value":{"entity-type":"item","numeric-id":4485697,"id":"Q4485697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1854567$489AB5F1-BB9B-463F-B71E-87BE8F3447B2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29481a7cadcc8c753612932ad360f8be3403f9d0","datavalue":{"value":{"entity-type":"item","numeric-id":5311101,"id":"Q5311101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"becde6cf20623ccced4ff2130b2aa90250d179b7","datavalue":{"value":{"amount":"+0.8349134922027588","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":"Q1854567$54CF73E8-B81E-446E-A0C3-79DA1759723A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07a39b18793c1466eb4b6ce0aaa81b2c3330e8a4","datavalue":{"value":{"entity-type":"item","numeric-id":1399979,"id":"Q1399979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a91b3486a376e44656467a6e203700d747c27c3","datavalue":{"value":{"amount":"+0.8332489728927612","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":"Q1854567$E6BDC496-00D8-4877-A4DE-96EA64FE65C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5cece74fb838d26344413fb57a1cf3e943565a5","datavalue":{"value":{"entity-type":"item","numeric-id":4240341,"id":"Q4240341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a91b3486a376e44656467a6e203700d747c27c3","datavalue":{"value":{"amount":"+0.8332489728927612","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":"Q1854567$A84D8ED9-5C67-4DEB-A848-13148488159B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"239f4a1c5a5370e6e7b02ebeaf57af692ea8f846","datavalue":{"value":{"entity-type":"item","numeric-id":867861,"id":"Q867861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71b656debfe785489ef4ec8c1f9c313eda39ebe0","datavalue":{"value":{"amount":"+0.8269650340080261","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":"Q1854567$2C472DDE-9DC3-49CB-BCB4-B4ED7BE94CAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4790a1492f6e007c2ab89259245f47db30064e7f","datavalue":{"value":{"entity-type":"item","numeric-id":4419798,"id":"Q4419798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e9ffe0fc1bde4ebf2fa91f24eee36da87beba4f","datavalue":{"value":{"amount":"+0.811529815196991","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":"Q1854567$2115EC46-0289-4DF5-B25E-D08D1A5CBA6B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the nonapproximability of Boolean functions by OBDDs and read-\\(k\\)-times branching programs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_nonapproximability_of_Boolean_functions_by_OBDDs_and_read-%5C(k%5C)-times_branching_programs"}}}}}