符号单项式凸性识别被证明为强NP难：三条可解性路径同时失效
相关研究与后续进展
核心概要
该工作研究符号单项式（实指数广义单项式的有限和）的凸性识别问题，证明判断一个符号单项式是否在原变量下凸、是否在对数变量变换后凸、以及在其为正时是否在再取对数值后凸（即纪律化几何规划所依赖的结构）这三种形式，在紧致域上和全局范围内均为强NP难，证明从多项式凸性的间隙-承诺变体出发，构造了在相应对数变换下保持曲率间隙的多项式到符号单项式的归约。
log-log convexity. Figure 1 summarizes these three notions and their relationships.
arXiv · 第 2 页深度剖析
论文证明符号单项式凸性识别的三种形式——原变量凸、对数变量变换后凸、以及正值情形下再取对数值后凸——均为强NP难。 此前符号单项式优化已知一般不可解，凸性被视为通向可解性的三条路径，但识别这些凸性结构本身的复杂度此前未被刻画；该工作把不可解性推进到识别环节。 摘要给出的是复杂度归约证明：从多项式凸性的间隙-承诺变体出发，构造保持曲率间隙的多项式到符号单项式归约，结论同时覆盖紧致域与全局两种设定。
论文指出符号单项式是自然的机器学习模型，兼具幂律、反比关系与乘法交互的简约表示、通用逼近能力与可解释参数。 该观察把符号单项式从传统工程优化对象提升为机器学习表示形式，并给出AI Feynman基准中100个方程有45个可写成符号单项式这一量化证据。 依据为摘要中陈述的基准统计（100个方程中45个）与对符号单项式表示性质的说明，属于对既有表示能力的归纳而非新实验。
论文的归约技术核心是在相关对数变换下保持曲率间隙，从而把多项式凸性的间隙-承诺难度传递到符号单项式凸性识别。 这一归约方式使对数变换（以及对数值的对数）不再能作为绕过难度的通用手段，为三条路径给出统一的难度来源。 摘要明确说明证明起点为多项式凸性的间隙-承诺变体，并强调归约保持曲率间隙；具体构造细节未在摘要中展开。
启示与展望
该结果适用于符号单项式这一函数类，覆盖原变量凸、对数变量变换后凸、以及正值时对数值取对数后凸三种识别形式，并同时针对紧致域与全局设定。对从事几何规划、工程设计与机器学习符号回归的研究者，这意味着不能指望通用算法在多项式时间内判定这些凸性；可行的方向是限定结构化子类、采用近似或数值判定，或直接使用不依赖凸性识别的全局方法。
摘要未给出归约的具体构造、间隙参数与证明步骤，也未说明结论对受限子类（如低维、稀疏或特定指数结构）是否仍然成立；此外，AI Feynman基准中45/100这一统计的判定标准与覆盖范围在摘要中未展开。这些属于摘要层面的信息边界，完整论文中的定理陈述与证明细节仍需查阅原文确认。