新论文证明ReLU网络验证问题在参数化复杂度上为W[ℓ-1]-hard，枚举法近乎最优
研究人员解决了Froese等人提出的开放问题，证明对于ℓ层ReLU网络，正性判定等验证问题在输入维度参数化下是W[ℓ-1]-hard，相关计算几何问题zonotope非包含为W[1]-hard。
AI解读：神经网络验证的难点在于：即使输入维度固定，检查网络是否满足某些性质（如输出恒为正）的计算开销可能指数增长，难以扩展。这篇arXiv论文的核心价值是从理论层面划定了边界——它证明了对于任意ℓ≥2层的ReLU网络，在输入维度参数化下，判定正性等问题属于W[ℓ-1]-hard复杂度类，而现有枚举算法运行时间n^((ℓ-1)d)·poly(N)在指数时间假设下几乎最优。这意味着，如果这些假设成立，找不到根本更快的通用验证算法，行业只能依赖近似方法或针对特定结构的启发式。对使用ReLU网络的安全关键系统开发者（如自动驾驶、机器人控制）来说，这项结果提醒他们：对高维网络的严格验证可能在计算上不可行，需在设计阶段就考虑可验证性（如限制层数或维度），或接受近似验证的误差。普通读者无需立即行动，但可理解神经网络并非总能被有效检查。
arXiv论文（编号2509.22849v3）证明了ReLU神经网络若干验证问题的参数化复杂度下界，解决了Froese等人[COLT '25]提出的开放问题。作者为Vincent Froese, Moritz Grillo, Christoph Hertrich和Moritz Stargalla。
核心结果：对于所有ℓ≥2，判定一个由ℓ层ReLU网络计算的函数f:R^d→R是否为正（因此也判定其是否满射）在输入维度d参数化下是W[ℓ-1]-hard。
与几何和机器人问题的联系
当ℓ=2时，上述结果意味着zonotope非包含问题在环境维度d下是W[1]-hard。该问题在计算几何、控制理论和机器人学中有独立重要性。
其他验证问题的难度
对任意乘性因子近似ℓ层网络的最大值，以及计算p∈(0,∞]时的L_p-Lipschitz常数，在d参数化下都是NP-hard和W[ℓ-1]-hard。
对于ℓ≥3，近似L_p-Lipschitz常数是NP-和W[ℓ-2]-hard。此外，当d为常数时，上述问题以ℓ为参数对所有t≥1都是NP-和W[t]-hard。
对现有算法的影响
作者指出，这些困难性结果意味着，针对这些基本问题的朴素枚举方法（运行时间为n^((ℓ-1)d)·poly(N)）在指数时间假设下本质上是最优的。