# NP-Hard Lower Bound Complexity for Semantic Self-Verification

arXiv: https://arxiv.org/abs/2501.15446 · HTML: https://mlsanity.com/paper/2501.15446/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 45 references that are in the map.
- First posted on arXiv 26 Jan 2025.

## Builds on (most cited first, 17 of 17)

- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Learning to summarize from human feedback](https://mlsanity.com/paper/2009.01325/) (2020)
- [Red Teaming Language Models with Language Models](https://mlsanity.com/paper/2202.03286/) (2022)
- [Aligning AI With Shared Human Values](https://mlsanity.com/paper/2008.02275/) (2020)
- [RLAIF vs. RLHF: Scaling Reinforcement Learning from Human Feedback with AI Feedback](https://mlsanity.com/paper/2309.00267/) (2023)
- [AI safety via debate](https://mlsanity.com/paper/1805.00899/) (2018)
- [Using Pre-Training Can Improve Model Robustness and Uncertainty](https://mlsanity.com/paper/1901.09960/) (2019)
- [Cooperative Inverse Reinforcement Learning](https://mlsanity.com/paper/1606.03137/) (2016)
- [Algorithms for Verifying Deep Neural Networks](https://mlsanity.com/paper/1903.06758/) (2019)
- [Why AI is Harder Than We Think](https://mlsanity.com/paper/2104.12871/) (2021)
- [Penalizing side effects using stepwise relative reachability](https://mlsanity.com/paper/1806.01186/) (2018)
- [OVERT: An Algorithm for Safety Verification of Neural Network Control Policies for Nonlinear Systems](https://mlsanity.com/paper/2108.01220/) (2021)
- [Embedded Agency](https://mlsanity.com/paper/1902.09469/) (2019)
- [Efficient Global Robustness Certification of Neural Networks via Interleaving Twin-Network Encoding](https://mlsanity.com/paper/2203.14141/) (2022)
- [When and Why is Persuasion Hard? A Computational Complexity Result](https://mlsanity.com/paper/2408.07923/) (2024)

## Built on by (most cited first, 1 of 1)

- [Knowledge Divergence and the Value of Debate for Scalable Oversight](https://mlsanity.com/paper/2603.05293/) (2026)

## Abstract (arXiv)

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.