.png){kind=icon}
返回
Symmetric Arithmetic Circuits
.png){kind=icon}
PRE
AI
DOI：10.4086/toc.2025.v021a014.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
我们引入了对称算术电路，即带有自然对称性限制的算术电路。在计算由变量矩阵定义的多项式（如行列式或永久式）的电路背景下，该限制要求电路的形状在矩阵的行和列同时置换下保持不变。我们证明了计算永久式的任何对称电路的规模存在无条件指数下界。相比之下，我们展示了在特征为零的域上计算行列式的对称电路存在多项式规模的电路。
Keyword:
arithmetic circuits
algebraic circuits
symmetric circuits
determinant
permanent
lower bounds
descriptive complexity
circuit complexity
matching
