证明了语义自验证在简单情形下已是计算难题，影响AI安全与对齐设计。
NP-Hard Lower Bound Complexity for Semantic Self-Verification
- 将语义自验证建模为逻辑可满足性问题，通过3-SAT归约证明其NP完全性。
- 即使简化场景中，该问题也存在不可逾越的计算复杂度下界。
- 适用于关注AI指令理解与对齐的系统，尤其宪法式AI和自然语言对齐研究者。
我们将语义自验证（SSV）建模为在给定解释框架下判断陈述是否准确描述自身语义属性的问题，这涉及人工智能安全与公平性的核心挑战：AI能否验证自己正确理解了约束其行为的规则？我们通过从3-可满足性（3-SAT）到SSV的多项式时间归约，证明了在此设定下SSV是NP完全的。该归约将一个3-SAT公式映射为包含二值歧义术语及由逻辑子句导出的语义约束的SSV实例。这一结果表明，即便是简化的语义自验证形式也面临计算障碍。该NP完全性下界对依赖指令语义解释的AI安全与公平方法具有深远影响，包括但不限于宪法式AI、基于自然语言的对齐以及指令遵循系统。依赖AI自我验证理解的方案可能遭遇此类计算瓶颈。我们认为更现实的验证场景可能面临更高复杂度。
原文摘要 · Abstract (English)
We model Semantic Self-Verification (SSV) as the problem of determining whether a statement accurately characterizes its own semantic properties within a given interpretive framework that formalizes a challenge in AI safety and fairness: can an AI system verify that it has correctly interpreted rules intended to govern its behavior? We prove that SSV, in this specification, is NP-complete by constructing a polynomial-time reduction from 3-Satisfiability (3-SAT). Our reduction maps a 3-SAT formula to an instance of SSV involving ambiguous terms with binary interpretations and semantic constraints derived from logical clauses. This establishes that even simplified forms of semantic self-verification should face computational barriers. The NP-complete lower bound has implications for AI safety and fairness approaches that rely on semantic interpretation of instructions, including but not limited to constitutional AI, alignment via natural language, and instruction-following systems. Approaches where an AI system verify its understanding of directives may face this computational barrier. We argue that more realistic verification scenarios likely face even greater complexity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。