深度三布尔电路超越平方根指数
Beyond the Square-Root Exponent for Depth-Three Boolean Circuits
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
稿件构造一个确定性多项式时间语言，其n位成员函数在无界扇入OR–AND–OR电路中需要2^{ω(√n)}个门。摘要表示，该界在每个充分大输入长度成立，并计数所有门包括底层。该结果属于计算复杂性理论中的电路下界。
- 构造确定性多项式时间语言，其成员函数需2^{ω(√n)}个门。
- 下界适用于无界扇入OR–AND–OR电路并计数所有门。
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
We construct a language in deterministic polynomial time whose n-bit membership function requires $`2^{\omega(\sqrt n)}`$ gates in an unbounded-fan-in OR–AND–OR circuit. The bound holds at every sufficiently large input length and counts all gates, including the bottom layer.
用户标记：未标记
固定编号：8325038668ecf90c
原文来源