用强化学习找多项式最小算术电路，成功率超90%。
FactorLibrary: From Polynomials to Circuits via Recursive Subgoals
- 分步构建：从底层因子库出发，递归生成可复用子目标。
- 最高成功率达91.8%，在复杂度8以内找到最优解。
- 适合研究代数复杂性与自动电路优化的学者。
在有限域上寻找多项式的最小算术电路是代数复杂性理论中的一个组合难题。本文将其建模为双向强化学习问题：自底向上和自顶向下。为应对搜索空间快速膨胀的挑战，提出FactorLibrary，存储可分解的子表达式作为跨训练轮次的可复用子目标。训练了基于Gumbel-PPO-MCTS的自底向上智能体，以及基于PPO+MCTS和SAC的两个自顶向下智能体。其中PPO+MCTS自顶向下智能体表现最稳定，在复杂度8以内以91.8%的成功率找到经认证的最优电路。
原文摘要 · Abstract (English)
Finding minimal arithmetic circuits for polynomials over finite fields is a combinatorially hard problem central to algebraic complexity theory. We formulate it as a reinforcement learning problem in two directions, bottom-up and top-down. To address the challenge of a fast-growing combinatorial search space, we introduce FactorLibrary, which stores factorizable subexpressions that serve as reusable subgoals across training episodes. We trained a bottom-up agent with Gumbel-PPO-MCTS and two top-down agents with PPO+MCTS and SAC. The PPO+MCTS top-down agent exhibited the most stable performance, finding certified optimal circuits up to complexity $8$ with a success rate of $91.8\%$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。