AC0 电路类

AC0是电路复杂度理论中的一个复杂度类,指能由常数深度、多项式规模的布尔电路计算的函数族,这些电路使用扇入不受限制的与门、或门以及非门。它是并行计算和电路下界研究中最基础的类别之一。

概述

AC0对应于可高度并行、层数固定的浅层电路计算。由于门的扇入没有限制,一层就能对任意多个输入取合取或析取,但深度必须是常数,这一约束严重限制了它的计算能力,也使它成为少数能被严格证明下界的复杂度类。

核心特点

• 电路深度为不依赖输入规模的常数。
• 电路规模即门的总数是输入规模的多项式。
• 与门和或门允许任意大的扇入,非门通常只作用于输入。
• 著名结果表明奇偶函数不属于AC0,即常数深度多项式电路无法计算输入中一的个数的奇偶性。
• 该下界最初由弗斯特、萨克斯、西普塞等人证明,后经哈斯塔德用切换引理给出更强形式。

应用场景

AC0的研究推动了整个电路下界理论的发展,是理解并行计算能力边界的窗口。切换引理等技术从这里发端,后来被推广到更大的电路类。AC0下界还与一阶逻辑的表达能力、伪随机性构造以及计算学习理论中的可学习性结果密切相关,例如AC0函数在均匀分布下可被高效近似学习。

常见问题

问:为什么奇偶函数不属于AC0如此重要?答:它是最早的自然函数无条件电路下界之一,无需任何未证假设就说明常数深度电路能力有限,标志着人类首次真正证明某类电路算不出某个具体函数。

问:AC0和TC0有何区别?答:TC0在AC0的门之外还允许多数门或阈值门,这使TC0能计算奇偶和多数等AC0算不出的函数,因此TC0严格包含AC0。