本文研究了二值化神经网络（BNN）验证问题的计算复杂性。研究人员通过将布尔可满足性问题（SAT）归约到二值化神经网络可满足性问题，证明了其NP-完全性。此外，他们发现均匀图像遮挡会导致分段常数网络输出，从而允许使用多项式时间算法来检查鲁棒性。 AI
影响 确立了二值化神经网络验证的理论极限，可能指导未来在高效和鲁棒模型设计方面的研究。
排序理由 该集群包含一篇详细介绍二值化神经网络计算复杂性结果的学术论文。
AI 生成摘要 · Google Gemini · 来自 2 个来源。 我们如何撰写摘要 →
arXiv:2606.18918v1 Announce Type: new Abstract: This paper studies the computational complexity of verification problems for Binarized Neural Networks (BNNs), where activations (and sometimes weights) are binary. We analyze two problems: satisfiability and robustness under unifor…
This paper studies the computational complexity of verification problems for Binarized Neural Networks (BNNs), where activations (and sometimes weights) are binary. We analyze two problems: satisfiability and robustness under uniform image occlusion. We show that BNN satisfiabili…