布尔函数的判定树复杂性及问题

来源 :数学研究与评论 | 被引量 : 0次 | 上传用户:cmudh134
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
设f(x1,x2,…,xn)是一个布尔函数。如果计算f(x1,x2,…,xn)的每个判定定树算法在最坏情况下都要检查所有n个变量才能求得f的值,则称f是诡秘函数。1988年,A.C.C.Yao提出一个问题:如果一个单调非平凡的布尔函数f(x1,x2,…,xn)在循环群Cm×Cn的直积的可迁作用下不变,则f是诡秘的吗?对这个问题的肯定回答支持著名的Rivest-Vuillemin猜想。本文将部分地解答这一问题。
其他文献
我们国家已进入了社会主义市场经济的新阶段。在这一条件下,新闻工作如何坚持党性原则,是一个值得探讨和深思的问题。笔者就此问题谈一点粗浅的看法。服务市场经济与坚持新闻
目的:探讨血气分析时塑料和玻璃注射器内冷藏全血标本的氧分压(PO2)变化。方法:应用血气分析仪检测塑料和玻璃注射器冷藏全血标本PO2。结果:塑料注射器内全血贮存标本PO2随贮存
本文讨论由Beattie通过群代数的Ore扩张所构造的量子群的中心和Yang-Baxter模糊畴。此外,完全刻画了这类量子群的不可约表示。
对于有限级广义Dirichlet级数所表示的整函数f(s),引进级ρR,型τR,分别讨论它们与在水平直线上的级ρR,型τR之间的关系。应用于Taylor级数时,有类似结果。
本文证明了一个集合论性质的引理,由它可直接得出GSdel不完全性定理的抽象形式.文中还述及该引理的有关诸推论.
资源发现在对等网络研究中占有十分重要的地位,如何高效地搜索对等网络上的资源是对等网络实现最为关键的问题。基于对等网络的特点以及优势,给出对等网络的基本概念及分类,并系
本文给出了Dedekind群的一个刻画。即如果一个群G有一个无不动点的弱幂同构,则G是一个Dedekind群。
目的:探讨缓释异搏定治疗飞行员高血压的有效性。方法:采用单剂缓释异搏定对21例飞行员高血压症进行治疗,每日240mg早餐后顿服,观察血压、心率、心电图、血脂、脂蛋白亚组分和心
2014年之后的10年当中,巴西可能取代英国和法国成为世界第五大经济体。    对于腾飞中的拉丁美洲而言,它们面临的最大风险是傲慢。  时间回到2003年,当时,高盛的经济学家们将巴西和俄罗斯、印度、中国一起看作是即将主导世界的经济体,对于金砖四国BRIC中的B(巴西,Brazil),有着诸多非议——巴西?一个增长率如泳衣般单薄的国家,每一次金融危机的牺牲者,一个长期政治动荡的地方,挥霍自己明显潜
随着社会的发展,我区以拉萨为中心的各主要城镇的城市雕塑热正悄然兴起。 城市雕塑一般是指在城市的街心、公园,公共建筑前面及纪念意义的场所,根据不同地点设计的不同雕塑