电路复杂性

✍ dations ◷ 2025-12-10 12:37:10 #计算复杂性理论

电路复杂性理论在1990年代以前，被众多研究者认为是解决NP与P关系问题的可能的途径之一。电路复杂性研究的对象是非一致性的计算模型电路，并考虑计算一个布尔函数所需的最小的电路的深度（depth）和大小（size）等资源。其中，大小为多项式大小的电路族可以计算的布尔函数被记为P/poly。可以证明，P包含在P/poly之中，而卡普-利普顿定理（Karp-Lipton theorem）表明若P/poly在NP之中，则多项式层级（polynomial hierarchy）将会坍缩至第二层，这是一个不大可能的结果。这两个结果结合起来表明，P/poly可以当作是分离NP与P的一个中间的工具，具体的途径就是证明任一个NP完全问题的电路大小的下界。在直观上说，电路复杂性也绕过了NP与P问题的第一个困难：相对化证明困难（relativizing proofs）。

在1980年代，电路复杂性途径取得了一系列的成功，其中包括奇偶性函数（Parity function）在 $AC^{0}$ $AC^{0}$ 中的下界为指数，以及团问题（clique problem）在单调性电路（monotone circuit）中的下界为指数。然而在1994年Razborov和Rudich的著名论文自然性证明（Natural proof）中指出，上面所用证明电路下界的方法，在单向函数存在的前提下是不可能分离NP和P的。该结果使很多专家对证明电路下界来分离NP和P的前景表示不乐观。

分支程序是电路复杂性的一个研究方向。

算术电路某种程度上可以看作布尔电路的代数版本。与布尔电路计算一个布尔函数不同，它计算的是一个在一个特定域上的多项式。

相关

载体蛋白载体蛋白（英语：carrier protein）简称“载体”，是参与离子、小分子或高分子跨越生物膜进行运输的一类多回旋折叠蛋白质。载体蛋白都是跨膜蛋白，它们能在协助扩散或主动运输过程中
亚硝胺亚硝胺、亚硝酸胺（Nitrosamine）是一类通式为R1N(–R2)–N=O的胺化合物，其大部分成员都属强致癌物。亚硝胺广泛应用于化妆品、杀虫剂与树脂的生产。其中N,N'-二亚硝基五亚甲基四
多面体多面体（polyhedron）是指三维空间中由平面和直边组成的几何形体。英文 polyhedron 源于古希腊语 πολύεδρον，由poly-（词根 πολύς，多）和 -hedron（έδρα，基底、座、面）
曹楚南曹楚南（1930年8月15日－），江苏常熟人，腐蚀科学与电化学学家，中国科学院院士。曹楚南1948年考入同济大学化学系。1952年毕业后任职于中国科学院上海分院物理化学研究所。次年随研究
类似物醇类似物是泛指任何有类似于醇类或羟基结构的有机化合物，例如硫醇、酚等。大部分的醇类似物都有类似的性质，例如易挥发和刺激性等性质。酚是一种具有羟基的芳香烃，不属于醇类，但
托马斯·贝叶斯托马斯·贝叶斯（英语：Thomas Bayes，约1702年－1761年4月17日），18世纪英国数学家。1742年成为英国皇家学会会员。贝叶斯以其在概率论领域的研究闻名于世，他提出的贝叶斯定理对于现代
河滨县里弗赛德县（英语：Riverside County）或称河滨县是美国加利福尼亚州南部的一个县，东邻亚利桑那州。面积18,915平方公里，根据美国2010年人口普查数字，共有人口2,189,641人。县治为河
特文特大学特文特大学（荷兰语：Universiteit Twente，荷兰语发音：；英语：University of Twente），曾译名为屯特大学，位于荷兰东部最大城市恩斯赫德，距离首都阿姆斯特丹2小时车程，是荷兰教育部直属重点
苏格兰牧羊犬苏格兰牧羊犬（Rough Collie）从英文字义上看又被称为粗毛牧羊犬，而可利牧羊犬是常见的俗称。此类犬种为历史悠久的牧羊犬，原产于苏格兰。因为知名电视剧《灵犬莱西》而广为众人所
阿里列沙·查汉巴殊阿里列沙·查汉巴殊（波斯语：‌ علیرضا جهانبخش جیرنده‎，1993年8月11日－），是一名伊朗职业足球运动员，司职右翼前锋。现在效力于英格兰足球超级联赛球队布莱顿。